# Fibonacci sequence

• Jun 4th 2008, 04:36 AM
woollybull
Fibonacci sequence
Could someone please help me with this. Use the pascal sequence property nCr + nC(r+1) = (n+1)C(r+1) to explain why F3 + F4 = F5 and F4 + F5 = F6.
Given that Fn = nC0 +(n-1)C1 +...+ 1C(n-1) + 0Cn.

What I tried was to expand out F3, F4, F5 and F6 and then use the pascal sequence on terms which had r higher than 0.
For example. F6 = 6C0 +5C1 +4C2 +3C3 + 2C4 + 1C5 + 0C6.
By the pascal sequence 5C1 = 4C0 + 4C1 and 4C2 = 3C1 + 3C2 etc. But what should I do with terms where n is larger than r like 2C4 and 1C5??? I ditched them because they are meaningless. Fair enough?

Thanks in advance for any assistance.
• Jun 4th 2008, 05:48 AM
Isomorphism
Quote:

Originally Posted by woollybull
Could someone please help me with this. Use the pascal sequence property nCr + nC(r+1) = (n+1)C(r+1) to explain why F3 + F4 = F5 and F4 + F5 = F6.
Given that Fn = nC0 +(n-1)C1 +...+ 1C(n-1) + 0Cn.

What I tried was to expand out F3, F4, F5 and F6 and then use the pascal sequence on terms which had r higher than 0.
For example. F6 = 6C0 +5C1 +4C2 +3C3 + 2C4 + 1C5 + 0C6.
By the pascal sequence 5C1 = 4C0 + 4C1 and 4C2 = 3C1 + 3C2 etc. But what should I do with terms where n is larger than r like 2C4 and 1C5??? I ditched them because they are meaningless. Fair enough?

Thanks in advance for any assistance.

From your definition of $\displaystyle F_n$,

$\displaystyle F_n = \sum_{k=0}^{k=n} \binom{n-k}{k}$

So:
$\displaystyle F_{n-1} + F_n = \sum_{k=0}^{k=n-1} \binom{n-1-k}{k}+ \sum_{k=0}^{k=n} \binom{n-k}{k}$

$\displaystyle F_{n-1} + F_n = \sum_{k=0}^{k=n-1} \binom{n-k-1}{k}+ \binom{n}{0}+ \sum_{k=1}^{k=n} \binom{n-k}{k}$

Let k = t + 1 for the second summation:

$\displaystyle F_{n-1} + F_n = \sum_{k=0}^{k=n-1} \binom{n-k-1}{k}+ \binom{n}{0}+ \sum_{t=0}^{t=n-1} \binom{n-(t+1)}{t+1}$

But t is just a dummy variable, so let t=k:

$\displaystyle F_{n-1} + F_n = \binom{n}{0}+ \sum_{k=0}^{k=n-1} \binom{n-k-1}{k}+ \sum_{k=0}^{k=n-1} \binom{n-k-1}{k+1}$

$\displaystyle F_{n-1} + F_n = \binom{n}{0}+ \sum_{k=0}^{k=n-1}\left(\binom{n-k-1}{k}+\binom{n-k-1}{k+1}\right)$

Now use Pascal's identity $\displaystyle \binom{n-k-1}{k}+\binom{n-k-1}{k+1} = \binom{n-k}{k+1}$

Thus we get:
$\displaystyle F_{n-1} + F_n = \binom{n}{0}+ \sum_{k=0}^{k=n-1}\binom{n-k}{k+1}$

Again let k = t - 1:

$\displaystyle F_{n-1} + F_n = \binom{n}{0}+ \sum_{t=1}^{t=n}\binom{n-(t-1)}{(t-1)+1}$

So again t is just a dummy variable, so let t=k:
$\displaystyle F_{n-1} + F_n = \binom{n}{0}+ \sum_{k=1}^{k=n}\binom{n-(k-1)}{(k-1)+1}$

Since $\displaystyle \binom{n}{0} = \binom{n+1}{0}$

$\displaystyle F_{n-1} + F_n = \binom{n+1}{0}+ \sum_{k=1}^{k=n}\binom{(n+1)-k}{k}$

$\displaystyle F_{n-1} + F_n = \sum_{k=0}^{k=n}\binom{(n+1)-k}{k}$

But by definition,

$\displaystyle \sum_{k=0}^{k=n}\binom{(n+1)-k}{k} = F_{n+1}$

Thus:

$\displaystyle F_{n-1} + F_n = \sum_{k=0}^{k=n}\binom{(n+1)-k}{k}= F_{n+1}$
• Jun 4th 2008, 05:54 AM
Isomorphism
Quote:

Originally Posted by woollybull
But what should I do with terms where n is larger than r like 2C4 and 1C5??? I ditched them because they are meaningless. Fair enough?

I think the definition is $\displaystyle \binom{n}{k} = 0$, when $\displaystyle k > n$ and it makes sense if we define $\displaystyle \binom{n}{k}$ as number of ways of choosing k objects from n objects.
• Jun 4th 2008, 08:47 PM
woollybull
The text hasnt covered summation signs and I think they are looking for a very simple proof which is why they just used F3 + F4 = F5 and F4 + F5 = F6 as an example to show.
• Jun 4th 2008, 11:15 PM
Isomorphism
Quote:

Originally Posted by woollybull
The text hasnt covered summation signs and I think they are looking for a very simple proof which is why they just used F3 + F4 = F5 and F4 + F5 = F6 as an example to show.

The summation signs are nothing extraordinary. Instead of writing all the terms of the sum, we write it like that. To understand the proof, you can expand it and write the individual terms at every step. I suggest you try that.

$\displaystyle F_3 = \binom{3}{0}+\binom{2}{1}+\binom{1}{2}+\binom{0}{3 }$

$\displaystyle F_4 = \binom{4}{0}+\binom{3}{1}+\binom{2}{2}+\binom{1}{3 }+\binom{0}{4}$

$\displaystyle F_3 + F_4 = \binom{3}{0}+\binom{2}{1}+\binom{1}{2}+\binom{0}{3 } +\binom{4}{0}+\binom{3}{1}+\binom{2}{2}+\binom{1}{ 3}+\binom{0}{4}$

Now group the terms like this:

$\displaystyle F_3 + F_4 =\binom{4}{0}+ \left(\binom{3}{0}+\binom{3}{1}\right)+\left(\bino m{2}{1}+\binom{2}{2}\right)+\left(\binom{1}{2}+\bi nom{1}{3}\right)+\left(\binom{0}{3} +\binom{0}{4}\right)$

Now use Pascal's Identity on the grouped terms:

$\displaystyle F_3 + F_4 =\binom{4}{0}+ \binom{4}{1}+\binom{3}{2}+\binom{2}{3}+\binom{1}{4 }$

Note 2 things:
1) $\displaystyle \binom{0}{4} = 0$, so we can add it to the sum without affecting the equality.

2) $\displaystyle \binom{4}{0} = \binom{5}{0}$, so we can replace $\displaystyle \binom{4}{0}$ by $\displaystyle \binom{5}{0}$

$\displaystyle F_3 + F_4 =\binom{5}{0}+ \binom{4}{1}+\binom{3}{2}+\binom{2}{3}+\binom{1}{4 }+\binom{0}{5}$

But by definition, $\displaystyle F_5 =\binom{5}{0}+ \binom{4}{1}+\binom{3}{2}+\binom{2}{3}+\binom{1}{4 }+\binom{0}{5}$

Thus:

$\displaystyle F_3 + F_4 =\binom{5}{0}+ \binom{4}{1}+\binom{3}{2}+\binom{2}{3}+\binom{1}{4 }+\binom{0}{5}=F_5$