# what is the value of the following sum?

I would like to get the value of the following: $$\frac{1}{2^{n-1}} \sum_{k \ge 0} \binom {n}{2k} 5^k.$$ This comes from the computation of the trace of certain matrix.

$$\sum_{k \ge 0} \binom {n}{2k} (\sqrt{5})^{2k} + \sum_{k \ge 0} \binom {n}{2k+1} (\sqrt{5})^{2k+1} = (1+\sqrt{5})^n$$
$$\sum_{k \ge 0} \binom {n}{2k} (\sqrt{5})^{2k} - \sum_{k \ge 0} \binom {n}{2k+1} (\sqrt{5})^{2k+1} = (1-\sqrt{5})^n$$
• In fact, I was trying to find the value of $[ (1+ \sqrt{5})/2 ]^n + [(1- \sqrt{5})/2]^n .$ – hkju Nov 4 '14 at 21:16