Fibonacci & Pascal's Triangle Proof

[swtster]

I've been working on the following problem for the last two days and I can't seem to get anywhere. I've done the problem in countless ways but none seem to work out.

This is the problem:

Consider any row of Pascal's triangle. Multiply the entries of the row by successive Fibonacci numbers and add the results. For example, for the fifth row "1, 5, 10, 10, 5, 1", the associated sum is:

. . .1 × 1 + 5 × 1 + 10 × 2 + 10 × 3 + 5 × 5 + 1 × 8 = 89

Find the general case of this formula and prove it using mathematical induction.

Here is what I have so far:

My work:
Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233...

3rd row: 1 × 1 + 3 × 1 + 3 × 2 + 1 × 3 = 13

8th row: 1 × 1 + 8 × 1 + 28 × 2 + 56 × 3 + 70 × 5 + 56 × 8 + 28 × 13 + 8 × 21 + 1 × 34 = 1597

General Case:
The sum of the nth row is equal to the (2n+1) term in the Fibonacci sequence.
Therefore,

. . .sum[i=1 to n][C(n,i-1)F(i)] + C(n,i)F(i+1) = F(2n+1)

Step 1: show that it is true for n=1

LS:

. . .sum[i=1 to n][C(n,i-1)F(i)] + C(n,i)F(i+1)

. . . . . . .= C(1,0)F(1) + C(1,1)F(2)

. . . . . . .= (1)(1) + (1)(1)

. . . . . . .= 2

RS:

. . .F(2n+1)

. . . . .= F(3)

. . . . .= 2

Therefore, it is true for n = 1.

Step 2: Assume it is true for n = k. Therefore, we assume:

. . .sum[i=1 to k][C(k,i-1)F(i)] + C(k,i)F(i+1) = F(2k+1)

Step 3: Prove it is true for n = k+1 using the assumption made in step 2.

Therefore, we want to prove:

. . .sum[i=1 to k+1][C(k+1,i-1)F(i)] + C(k+1,i)F(i+1) + C(k+1, i+1)F(i+2) = F(2(k+1)+1)

This is where I'm stuck. If I use the assumption from step 2, then the formula would be changed because I would be dealing with two different rows in the triangle instead of just one.

Any help would be greatly appreciated. Thanks in advance!

Note: This is for my summative due tomorrow, so it is quite urgent.

 

[pka]

There are literally hundreds of relationships between and among Fibonacci Numbers and the Pascal Triangle. I have seen this same question posted at other ‘help’ sites. With much the same answer as I am giving you. You proof depends upon one of those many special relationships. Most likely, only the person who wrote this question knows the secret. But you can look. Start at these sites.

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html
http://mathworld.wolfram.com/FibonacciNumber.html
http://math.holycross.edu/~davids/fibonacci/fibonacci.html
http://en.wikipedia.org/wiki/Fibonacci_number