we can prove by induction that u_n= 2^p(n) +1/2^p(n) for a funtion p:N->N_0 ( N union {0}) which satisfies the equations: (1) p(n+1) = p(n) +2p(n-1) (2) (-1)^(n-1)=p(n)-2p(n-1) (3) p(0)=0 , p(1)=1 and then solve that system to get the result. sorry for non-latex text : /

Is there any complete solution ???

My solution: The first few values are easily verified to be $2^{r_{n}}+2^{-r_{n}}$, where $r^{0}=0,r_{1}=r_{2}=1,r_{3}=3,r_{4}=5,r_{5}=11$,... Let us put $u_{n}=2^{r_{n}}+2^{-r_{n}}$ (we will show that $r_{n}$ exists and is integer for each $n$). A simple calculation gives us $u_{n}(u^{2}_{n-1}-2)=2^{r_{n}+2r_{n-1}}+2^{-r_{n}-2r_{n-1}}+2^{r_{n}-2r_{n-1}}+2^{-r_{n}+2r_{n-1}}$. If an array $q_{n}$, with $q_{0}=0 and q_{1}=1$, is set so as to satisfy the linear recurrence $q_{n+1}=q_{n}+2q_{n-1}$, then it also satisfies $q_{n}-2q_{n-1}=-(q_{n-1}-2q_{n-2})=...=(-1)^{n-1}(q_{1}-2q_{0})$. Assuming inductively up to $n r_{i}=q_{i}$, the expression for $u_{n}(u^{2}_{n-1}-2) =u_{n+1}+u_{1}$ reduces to $2^{q_{n}+1}+2^{-q_{n}+1}+u_{1}$. Therefore, $r_{n+1}=q_{n+1}$. The solution to this linear recurrence with $r_{0}=0, r_{1}=1 is r_{n}=q_{n}=\frac{2^{n}-(-1)^{n}}{3}$, and since $[u_{n}]=2^{r_{n}}$ for $n\geq 0$, the result follow.