Prove that a certain sum of binomial coefficients is divisible by a power of 2

Question

As many will recognize the following expression is a closed form for the Fibonacci numbers. Can it be proved that
$$\frac{1}{2^{n-1}} \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n}{2j+1} 5^{j} \quad \text{where} \quad n \in\mathbb{N}$$ are integers without using the fact that these are the Fibonacci numbers?

Answer 1

By binomial theorem the expression is equivalent to: $$ S_n=\frac1 {2^{n}}\frac{(1+x)^n-(1-x)^n}x, $$ where $x=\sqrt5$. Since the latter fraction which we denote $Z_n (x)$ is clearly integer ($x $ cancels leaving in the numerator only even powers of $x $), we need only to prove that it is divisible by $2^{n}$. To prove this we proceed as follows: $$ 2 Z_n (x)=[(1+x)+(1-x)]Z_n (x)=Z_{n+1}(x)+(1-x^2)Z_{n-1}(x)\tag1 $$

Dividing (1) by $2^{n+1} $ and rearranging terms one obtains: $$ S_{n+1}=S_n+\frac {x^2-1}4S_{n-1}\tag2 $$

Since $S_0=0$ and $S_1=1$ the statement $S_n\in\mathbb Z$ follows by induction for all $n\ge0 $ provided that $4|(x^2-1) $ which is indeed true.

Answer 2

Let $$S_n=\frac{1}{2^{n-1}} \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n}{2j+1} 5^{j} \quad \text{where} \quad n \in\mathbb{N}$$

By binomial theorem $$2\sum_{k=0}^{n/2}{n\choose 2k+1} (\sqrt{5})^{2k}=(1+x)^n-(1+x)^n$$ $$S_n=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]=F_n$$ Where $F_n$ is Fibonacci number which is always a positive integer. Moreover, one may also check that $S_0=F_0=0$ and $S_1=1=F_1$.

Answer 3

Hint:

$$S_n=\frac{1}{2^{n-1}} \sum_{j=0}^{\lfloor n/2 \rfloor} \binom{n}{2j+1} (\sqrt{5})^{2j} \quad \text{where} \quad n \in\mathbb{N}$$ Use ${n \choose k}={n-1 \choose k}+{n-1 \choose k-1}$ $$\implies S_n=2^{n-1} \sum_{j=0}^{[n/2]}\left({n-1 \choose 2j} (\sqrt{5})^{2j}+{n-1 \choose 2j-1} \sqrt{5}^{2j}\right)$$ Next, these two parts can yield $S_n=S_{n-2}+S_{n-1}$ sfter interesting adjustments.

I hope to come back.