Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I found this problem in a math magazine:

Given the sequence $(x_n)_{n \in \mathbb{N}}$ defined by: $$ x_0 = 0\\ x_1 = 1\\ x_{n+2}+x_{n+1}+2x_{n}=0 $$ Prove that $s_n = 2^{n+1}-7x_{n-1}^2, n > 0$ is a square number.

I tried searching a rule between the numbers of the sequence and the square numbers ($s_n$) formed: $$ x_2=-1\\ x_3=-1\\ x_4=3\\ x_5=-1\\ x_6=-5\\ x_7=7\\ x_8=3\\ x_9=-17\\ $$ $$ s_1 = 2^2\\ s_2 = 1^2\\ s_3 = 3^2\\ s_4 = 5^2\\ s_5 = 1^2\\ s_6 = 11^2\\ s_7 = 9^2\\ $$ If I rewrite the rule and square it: $$ x_{n-1} = -x_{n-2}-2x_{n-3}, n > 3\\ x_{n-1}^2=x_{n-2}^2 + 4x_{n-3}^2 + 4x_{n-2}x_{n-3}\\ $$ apply for the next two, $x_{n-2}$, $x_{n-3}$ the same rule: $$ x_{n-2}^2=x_{n-3}^2 + 4x_{n-4}^2 + 4x_{n-3}x_{n-4}\\ x_{n-3}^2=x_{n-4}^2 + 4x_{n-5}^2 + 4x_{n-4}x_{n-5}\\ $$ substitute: $$ x_{n-1}^2=x_{n-3}^2 + 4x_{n-4}^2 + 4x_{n-3}x_{n-4}+4x_{n-3}^2 + 4x_{n-2}x_{n-3}\\ x_{n-1}^2=5x_{n-3}^2 + 4x_{n-4}^2 + 4x_{n-2}x_{n-3} + 4x_{n-3}x_{n-4} \\ x_{n-1}^2=5(x_{n-4}^2 + 4x_{n-5}^2 + 4x_{n-4}x_{n-5}) + 4x_{n-4}^2 + 4x_{n-2}x_{n-3} + 4x_{n-3}x_{n-4}\\ x_{n-1}^2=9x_{n-4}^2 + 20x_{n-5}^2 + 4x_{n-2}x_{n-3} + 4x_{n-3}x_{n-4} + 20x_{n-4}x_{n-5}\\ $$ It seems to lead to a dead end.

A help would be really appreciated.

share|improve this question
1  
Note that further to froggie's solution below, you need to be careful to pick the correct sign of the numbers you are squaring eg $s_2=(-1)^2$ - which makes the pattern easier to spot. –  Mark Bennet Dec 15 '12 at 15:48

1 Answer 1

up vote 6 down vote accepted

This may be a little brute force, but it's a solution:

If you're familiar with solving linear recurrences, you'll know that you can write a formula for the $x_n$ of the form $$x_n = A\lambda_+^n + B\lambda_-^n,$$ where $A$ and $B$ are constants and the $\lambda_\pm$ are the roots of the polynomial $x^2 + x + 2$, that is, $$\lambda_\pm = \frac{-1 \pm i\sqrt{7}}{2}.$$ Using the initial conditions $x_0 = 0$ and $x_1 = 1$, you can solve for the constants $A$ and $B$:$$ A = -B = \frac{-i}{\sqrt{7}}.$$ This then gives the explicit formula for the $x_n$:$$ x_n = \frac{-i}{\sqrt{7}}(\lambda_+^n - \lambda_-^n).$$ Now one has $$s_n = 2^{n+1} - 7x_{n-1}^2 = 2^{n+1} + (\lambda_+^{n-1} - \lambda_-^{n-1})^2 = 2^{n+1} + \lambda_+^{2(n-1)} + \lambda_-^{2(n-1)} - 2(\lambda_+\lambda_-)^{n-1}.$$ Using the fact that $\lambda_+\lambda_- = 2$, this becomes $$s_n = \lambda_+^{2(n-1)} + \lambda_-^{2(n-1)} + 2^n.$$ But then we can use $\lambda_+\lambda_- = 2$ again to write $$s_n = \lambda_+^{2(n-1)} + \lambda_-^{2(n-1)} + 2(\lambda_+\lambda_-)^{n-1} = (\lambda_+^{n-1} + \lambda_-^{n-1})^2.$$ Now it only remains to show that $\lambda_+^{n-1} + \lambda_-^{n-1}$ is an integer. Define $\alpha_n = \lambda_+^n + \lambda_-^n$ for each $n$. Then $\alpha_0 = 2$, $\alpha_1 = -1$, and $\alpha_{n+2} + \alpha_{n+1} + 2\alpha_n = 0$ for each $n\geq 2$, so $\alpha_n$ is an integer for all $n$. This completes the proof.

share|improve this answer
    
thank you for the solution –  animo Dec 15 '12 at 15:19

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.