Prove that the sum: \[ S_n=\binom{n}{1}+\binom{n}{3}\cdot 2005+\binom{n}{5}\cdot 2005^2+...=\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\binom{n}{2k+1}\cdot 2005^k \] is divisible by $2^{n-1}$ for any positive integer $n$.
Problem
Source:
Tags: floor function, combinatorics proposed, combinatorics
e.lopes
13.02.2006 00:29
I'm not certain about it, but i think that, if $A_n$ is the expression, $A_{n+2} = 2(A_{n+1} + 1002A_{n})$. so, the problem follows by induction. (is easy to see that $A_n = \frac{1}{2\sqrt{2005}}((1+ \sqrt{2005})^n - (1 - \sqrt{2005})^n)$)
Max(i)
25.12.2007 16:00
It's already quite old I know... but I want to post a sketch of my solution consider $ \frac{(\sqrt{2005}+1)^n}{\sqrt{2005}}=a_n+b_n*\sqrt{2005}$ so $ S_n = a_n$ $ \frac{(\sqrt{2005}+1)^n(\sqrt{2005}+1)}{\sqrt{2005}}=(a_n+b_n*\sqrt{2005})(\sqrt{2005}+1)$ so we get $ a_{n+1}=2005b_n+a_n$ and $ b_{n+1}=a_n+b_n$ now use indeuction
littletush
19.11.2011 08:01
$\frac{S_n}{2^{n-1}}=\frac{1}{\sqrt{2005}}[(\frac{1+\sqrt{2005}}{2})^n-\frac{1-\sqrt{2005}}{2})^n]$ is a integer,easily proved by recursion.
FriendPotato
07.04.2021 12:42
How do you reach to conclusion of that recurrence relations. Pls elaborate. I am unable to get that thing. Thanks in advance.