Prove that a certain sum of binomial coefficients is divisible by a power of 2 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?
 A: 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.
A: 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$.
A: 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.
