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;

So it's totally true