Fibonacci sequence

**woollybull** · June 4th 2008, 04:36 AM

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.

**Isomorphism** · June 4th 2008, 05:48 AM

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 $F_n$ ,

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

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

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

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

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

$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 $\binom{n-k-1}{k}+\binom{n-k-1}{k+1} = \binom{n-k}{k+1}$

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

Again let k = t - 1:

$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:
$F_{n-1} + F_n = \binom{n}{0}+ \sum_{k=1}^{k=n}\binom{n-(k-1)}{(k-1)+1}$

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

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

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

But by definition,

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

Thus:

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

**Isomorphism** · June 4th 2008, 05:54 AM

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 $\binom{n}{k} = 0$ , when $k > n$ and it makes sense if we define $\binom{n}{k}$ as number of ways of choosing k objects from n objects.

**woollybull** · June 4th 2008, 08:47 PM

Thanks for your help.
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.

**Isomorphism** · June 4th 2008, 11:15 PM

Originally Posted by woollybull

Thanks for your help.
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.

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

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

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

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

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

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

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

$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, $F_5 =\binom{5}{0}+ \binom{4}{1}+\binom{3}{2}+\binom{2}{3}+\binom{1}{4 }+\binom{0}{5}$

Thus:

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

Thread: Fibonacci sequence

LinkBack

Thread Tools

Display