Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am in the middle of writing my own math's paper on the topic of Pascal's Triangle. During the investigation I have came up with a formula for counting elements of Fibonacci Sequence using the entries from Pascal's Triangle (binomial coefficients). I know that there is a general formula for that (including floor of n), which I have explained, but what I also wanted to do in my work, was to create two formulas for counting even entries of Fibonacci Sequence and the odd ones. What I am struggling with however, is how to prove it using the induction. I attach the screenshot of the page that deals directly with ODD numbers. If you guys could help me with the proof either for even numbers, for odd or for the general formula, I would greatly appreciate it.


share|cite|improve this question
Please, I have been thinking about it already for 7 hours and can't find any solution :-( – Kbeski Mar 31 '14 at 16:53
Please turn the image into searchable text with math formatting. – MvG Apr 1 '14 at 8:57
up vote 3 down vote accepted

General term: $s_n = \displaystyle \sum_{0}^{\lfloor\frac{n-1}{2}\rfloor}\binom{n-1-r}{r} \text{ for } n \in \mathbb{N} \tag{1}$

I think you struggled because the binomial sum $s_{n+2}$ has a decomposition that involves both its even and odd numbered predecessors, and not just any one of them, as you were trying in the inductive step.

Decomposition: $s_{n+2} = s_{n+1} + s_{n} \tag{2}$

This is easy to prove by using the combinatorial identity $\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$. See here and here.

We can then use this property along with strong induction to prove:

$P(n): s_n = \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^n \text{ true } \forall n \in \mathbb{N}\tag{3}$


Base case: Show $P(1)$ and $P(2)$ to be true (by evaluating both sides).

Inductive step: Assume $P(n)$ and $P(n+1)$ true.

Then $\begin{aligned}s_{n+2} & = s_{n+1} + s_{n} \\ & = \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^{n+1} - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^{n+1} + \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^n \\ & = \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^n\left(\frac{3 + \sqrt{5}}{2}\right) - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^n\left(\frac{3 - \sqrt{5}}{2}\right) \\ & = \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^{n+2} - \frac{1}{\sqrt{5}}\left(\frac{1 - \sqrt{5}}{2}\right)^{n+2} \\ & \implies P(n+2) \text{ true }\end{aligned}$

This completes our proof. $ \blacksquare$

Note: The formulas for odd $n$ and even $n$ follow automatically from $(3)$ by the removal of the floor function in $s_n$.

share|cite|improve this answer
Hey Anant,Thanks a lot for your help. I have one question though, as I do not understand where did the (3+sqrt5/2) came from – Kbeski Apr 1 '14 at 10:53
@Kbeski: I factored out common terms and simplified. For example, $\begin{aligned} & \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^{n+1} + \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^{n} \\ = & \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^{n}\left( \frac{1 + \sqrt{5}}{2} + 1 \right) \\ = & \frac{1}{\sqrt{5}}\left(\frac{1 + \sqrt{5}}{2}\right)^{n}\left( \frac{3 + \sqrt{5}}{2} \right)\end{aligned}$ – Anant Apr 1 '14 at 11:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.