Hi,

I am trying to solve CSES Counting Towers and I'm having trouble finding what's wrong with my solution. I have described my process below, and it seems I am missing few combinations.

Let's call the number of combinations for 1xn towers a(n) and for 2xn towers b(n). Consider what the last blocks at the bottom of the tower are. We can have a 2xk block (k = 1 to n) at the end or one of the column having a 1xk block (k = 1 to n) at the end. In the first case, we will have b(n-k) variations. In the second case, the 1xk block can be on the left side and the right side. If one side has this 1xk block, then there are a(k) combinations of the other side. So our answer will be 2 * a(k). But we have double counted the combination of 2 1xk blocks. So actual answer is 2 * a(k) — 1. For each of these combinations of k blocks, there are b(n-k) variations.

Combining answers for both cases, we get b(n) = sum(k = 1 to n) 2 * a(k) * b(n-k). We can solve for a(k) to be = 1 << (k-1). Resulting in

b(n) = sum(k = 1 to n) (1 << k) * b(n-k) = 2 * b(n-1) + sum(k = 2 to n) (1 << k) b(n-k)

b(n) = 2 * b(n-1) + 2 * sum(k = 2 to n) (1 << k-1) b(n-k)
Use k = 1 + v and we find that the summation is just b(n-1)
So we get b(n) = 4 * b(n-1).

This is the wrong answer, and I am unable to find which combinations I am not counting. Please help! TIA!