Prove that for any positive integer $n$, the number \[ S_n = {2n+1\choose 0}\cdot 2^{2n}+{2n+1\choose 2}\cdot 2^{2n-2}\cdot 3 +\cdots + {2n+1 \choose 2n}\cdot 3^n \] is the sum of two consecutive perfect squares. Dorin Andrica
Problem
Source: Romanian IMO Team Selection Test TST 1999, problem 3
Tags: quadratics, modular arithmetic, induction, floor function, binomial coefficients, algebra, special factorizations
25.09.2005 00:44
Whenever I see a sum of alternate binomial coefficients I try to write it as $(X+Y)^n + (X-Y)^n$. In this case I think we get $S_n = \frac14 [ (2+\sqrt3)^{2n+1} + (2-\sqrt3)^{2n+1} ]$.
05.06.2009 05:05
Sketch of a solution that I have (I believe) worked out: Everything up to what rgep said is both natural and standard. Now, write \begin{eqnarray*}x^2 + (x + 1)^2 & = & \frac {(2 + \sqrt {3})^{2n + 1} + (2 - \sqrt {3})^{2n + 1}}{4} \\ & = & \frac {(1 + \sqrt {3})^{2(2n + 1)} + (1 - \sqrt {3})^{2(2n + 1)}}{2^{2n + 3}}\end{eqnarray*} The discriminant of the quadratic equation is $ \Delta = \left(\frac {(1 + \sqrt {3})^{2n + 1} + (1 - \sqrt {3})^{2n + 1}}{2^{n}}\right)^2$. Completing the square, we have $ x_{1,2} = \frac { - 2\pm\frac {(1 + \sqrt {3})^{2n + 1} + (1 - \sqrt {3})^{2n + 1}}{2^{n}}}{4}$ as the solutions to the above quadratic equation. It suffices to prove that $ x_{1,2}\in\mathbb{Z}$, i.e. $ (1 + \sqrt {3})^{2n + 1} + (1 - \sqrt {3})^{2n + 1}\equiv 2^{n + 1}\pmod{2^{n + 2}}$. You can prove (by induction for example) that \begin{eqnarray*}(1 + \sqrt {3})^{2n + 1} + (1 - \sqrt {3})^{2n + 1} & \equiv & \sqrt {3}((1 + \sqrt {3})^{2n + 1} - (1 - \sqrt {3})^{2n + 1}) \\ & \equiv & 2^{n + 1}\pmod{2^{n + 2}}\end{eqnarray*} The conclusion follows. $ \Box$ I hope that everything is correct.
05.06.2009 12:09
Lemma. If $ n \in \mathbb{N}$ then exist $ (x_n,y_n) \in \mathbb{N}^2$ such that $ (2 + \sqrt {3})^{2n + 1} = 1 + x_n^2 + y_n\sqrt {3}$. If it is true, then $ x_n$ is odd and since we have that $ S_n: = \frac {(2 + \sqrt {3})^{2n + 1} + (2 - \sqrt {3})^{2n + 1}}{4} = \frac {1 + x_n^2}{2} = z^2 + (z + 1)^2$ for $ x_n = 2z + 1$ then we have only to show that $ x_n$ is integer. But $ x_0$ and $ x_1$ are integers and $ x_n = \frac {1 + \sqrt {3}}{2}(2 + \sqrt {3})^n + \frac {1 - \sqrt {3}}{2}(2 - \sqrt {3})^n$ satisfies a recurrence of second order in integers.
06.06.2009 05:22
Dear rgep, boxedexe, bboypa , I'm sorry for my silly but I don' know how to get this rgep wrote: $ S_n = \frac14 [ (2 + \sqrt3)^{2n + 1} + (2 - \sqrt3)^{2n + 1} ]$. Could you make it clearer ? Thanks
11.06.2009 16:24
No one help me ? Just need to give me some hints or some links to further explain . Thanks.
11.06.2009 16:40
What happens if you multiply $ S_n$ by $ 2$ and treat $ 3^k$ as $ (\sqrt{3})^{2k}$? (Hint: Use Newton's Binomial Theorem). You can also determine the original thought process by expanding $ \frac{1}4 [ (2+\sqrt3)^{2n+1}+(2-\sqrt3)^{2n+1}]$ using Newton's Binomial Theorem, and determining what cancels in the process and how only terms with $ \binom{2n+1}{2k}$ remain. By going through this, you may learn how to use roots of unity to determine sums with forms resembling $ \sum_{k=0}^{\lfloor\frac{n}{m}\rfloor}\binom{n}{km}x^ky^{n-km}$, $ n\geq m>0$.
11.06.2009 16:40
forevercontinue wrote: No one help me ? Just need to give me some hints or some links to further explain . Thanks. Let $ S_n=\sum_{k=0}^{n}\binom{2n+1}{2k}2^{2n-2k}3^k$ $ 2S_n=\sum_{k=0}^{n}\binom{2n+1}{2k}2^{2n+1-2k}(\sqrt 3)^{2k}$ Let $ T_n=\sum_{k=0}^{n}\binom{2n+1}{2k+1}2^{2n+1-(2k+1)}(\sqrt 3)^{2k+1}$ $ 2S_n+T_n=\sum_{k=0}^{2n+1}\binom{2n+1}{k}2^{2n+1-k}(\sqrt 3)^{k}$ $ =(2+\sqrt 3)^{2n+1}$ $ 2S_n-T_n=\sum_{k=0}^{2n+1}\binom{2n+1}{k}2^{2n+1-k}(-\sqrt 3)^{k}$ $ =(2-\sqrt 3)^{2n+1}$ And so $ S_n=\frac 14((2+\sqrt 3)^{2n+1}+(2-\sqrt 3)^{2n+1})$
11.06.2009 17:19
Thanks boxedexe and pco too much . I appreciate your help.