prove: $\dfrac{2^{n+1}+(-1)^n}{3}$

Question

I am asked to prove this notation with induction for $n\in \mathbb{N}$:

real problem is to fill the area with tilings. and for $n\in \mathbb{N}$ there are exactly so many chances to fill the area as the formula says: $$\dfrac{2^{n+1}+(-1)^n}{3}$$

I started in this way:
Base Case: $n=1$:

$$\dfrac{ 2^2-1}{3} = 1$$

Inductive step: $n\rightarrow n+1$:

$$\dfrac{2^{n+2}+(-1)^{n+1}}{3} = help..$$

my problem is: what am i doing, i seem to have already proven it in this last step which is obviously wrong. what am i missing here in this proof?

thanks for help

Answer 1

$$\dfrac{2^{n+2}+(-1)^{n+1}}{3}$$ $$\dfrac{2^{n+1}\cdot2+(-1)^{n}\cdot(-1)}{3}$$ $$\dfrac{2^{n+1}\cdot2-(-1)^{n}}{3}$$ $$\dfrac{2^{n+1}\cdot(3-1)-(-1)^{n}}{3}$$ $$\dfrac{2^{n+1}\cdot(3)-2^{n+1}-(-1)^{n}}{3}$$ $$\dfrac{2^{n+1}\cdot(3)-(2^{n+1}+(-1)^{n})}{3}$$ $$\dfrac{2^{n+1}\cdot(3)}{3}-\dfrac{(2^{n+1}+(-1)^{n})}{3}$$

Proven.

Answer 2

Hint: $$\dfrac{2^{n+2}+(-1)^{n+1}}{3}=\dfrac{2^{n+1}+(-1)^n}{3}+\dfrac{2\cdot 2^n+2\cdot(-1)^{n-1}}{3}$$ (factorize the second term)

Answer 3

Looks like you would need the n - 1 case.

$2^{n+1} + (-1)^n = (2^{n+1} + (-1)^n)(2 + -1) = 2^{n+2} + 2(-1)^n + -2^{n+1} + (-1)^{n+1} = (2^{n+2} + (-1)^{n+1}) + 2(2^n + (-1)^{n-1}(-1)^2)$