You can't just put n+1 to it, you have to prove it

It means count all such words for n+1.

**1. Prove for N(0):**
There are only 3 "legitimate" values and N(0) = 3. So it's true!

**2. Prove for N(n+1) if we know that it's true for N(n)**
Let's count how many "legitimate" words could be for N(n+1):

a) We can construct "legitimate" word length n+1 by adding 1, 2 or 3 to "legitimate" word of length n, so there will be 3*N(n) such "legitimate" words;

b) By adding 0 to a non "legitimate" word of length n. There will be (2^2n-N(n)) such "legitimate" words of length n;

$\displaystyle N(n+1) = 3N(n)+(2^{2n}-N(n)) = 2^{2(n+1)-1}+2^{(n+1)-1}$

So it's totally true