Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

HELP

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

1 Answer 1

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}$

Proof-sketch:

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|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 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 at 11:17

Your Answer

 
discard

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.