You can use Newton's formula to develop and then study the 2 cases (n even and n odd).
When n is even all the terms involving disappear.
Certaintly, the terms of the sequence are integers.
Furthermore, the solution to this recurrence relation is given by: .
If is even then
Consider the Fibonacci sequence it satifies
If is odd then .
Therefore for odd we have .