Prove that $f(n)$ is the nearest integer to $\frac12(1+\sqrt2)^{n+1}$? Let $f(n)$ denote the number of sequences $a_1, a_2, \ldots, a_n$ that can be constructed where each $a_i$ is $+1$, $-1$, or $0$. 
Note that no two consecutive terms can be $+1$, and no two consecutive terms can be $-1$. Prove that $f(n)$ is the nearest integer to $\frac12(1+\sqrt2)^{n+1}$.
Can anyone help me with this problem. I really do not know what to do in this one.
 A: First, get the general formula for $f(n)$ in some way (OEIS is my favorite, see sequence A001333 which I found by generating the answers for small $n$'s; You could also do a singular value decomposition, or use generating function, or think about it combinatorically and deduce a formula from a recurrence relation).
$f(n)=\frac{(1-\sqrt{2})^{n+1}}{2} + \frac{(1+\sqrt{2})^{n+1}}{2}$.
You see, the first fraction is a number with absolute value smaller than $0.5$ for all $n>0$ (and it gets smaller and smaller).
A: Let $f_0(n)$ be the number of such sequences ending by $0$ and $f_1(n)$ be the number of such sequences ending by $1$ (number of such sequences ending by $-1$ is $f_1(n)$ too due to symmetry reason). Then $f_0(n) = f_0(n-1) + 2f_1(n-1)$, $f_1(n) = f_0(n-1) + f_1(n-1)$ and $f(n) = f_0(n) + 2f_1(n) = f_0(n+1)$. Some transformations: $f_0(n) - f_1(n) = f_1(n-1)$, $f_0(n) = f_1(n-1) + f_1(n)$, $f_1(n) = 2f_1(n-1) + f_1(n-2)$ and $f_1(0) = 0$, $f_1(1) = 1$. Solving this recurrent relation we get $\lambda^2 - 2\lambda - 1 = 0$, $\lambda_{1,2} = 1\pm \sqrt2$, $f_1(n) = c_1 \lambda_1^n + c_2 \lambda_2^n$.
$$\begin{cases}0 = c_1 + c_2,\\1 = c_1(1 + \sqrt 2) + c_2(1 - \sqrt 2);\end{cases} \begin{cases}c_1 = 1/(2\sqrt2),\\c_2 = -1/(2\sqrt2).\end{cases}$$
Then $f_1(n) = \frac1{2\sqrt2}\left((1+\sqrt2)^n - (1-\sqrt2)^n\right)$ and $$f(n) = f_0(n+1) = f_1(n+1) + f_1(n) =\\= \frac1{2\sqrt2}\left((1 + \sqrt2)^n(1 + 1 + \sqrt2) - (1 - \sqrt2)^n(1 + 1 - \sqrt2)\right) =\\= \frac12\left((1 + \sqrt2)^{n+1} + (1 - \sqrt2)^{n+1}\right).$$
The second summand is always less then $\frac12$.
