Pascal's Triangle and Fibonacci FormulaDate: 02/23/2002 at 18:22:22 From: Yael Subject: Proof of a theory The diagonals of Pascal's triangle give the Fibonacci numbers. As the numbers are also binomial coefficients, I wrote down some equations of the diagonals: (0,0) = 1 (1,0) = 1 (2,0)+(1,1) = 2 (3,0)+(2,1) = 3 (4,0)+(3,1)+(2,2) = 5 (5,0)+(4,1)+(3,2)=1+4+3 = 8 (6,0)+(5,1)+(4,2)+(3,3) = 1+5+6+1 = 13 (7,0)+(6,1)+(5,2)+(4,3) = 1+6+10+4 = 21 (8,0)+(7,1)+(6,2)+(5,3)+(4,4) = 1+7+15+10+1 = 54 so I tried to create a formula fib(n) = sum_{k=0}^{n/2} {n-1-k,k} I would like to know if this formula is correct. I looked this problem up on the Web and on R. Knott's site and found two unrelated formulas: fib(n) = sum_{k=0}^{n-1} {n-k-1,k} fib(n) = sum_{k=1}^{n} {n-k,k-1} I plugged in numbers and it didn't work. Maybe I'm wrong. I don't know. i then found a formula of lucas, 1876 F(n+1) = sum_{i=0}^{n/2} {n-i,i} n>=0 I think this is the same as mine, no? My thing to do was to prove why the diagonals of Pascal's triangle are the Fibonacci numbers by myself. Is what I did enough for 'my proof'? Thank you very much for taking your time. I think you do great jobs from what I've seen of the archives. Again, thank you for taking a look at 'my problem', if it is one! Yael Date: 03/04/2002 at 07:05:54 From: Doctor Floor Subject: Re: Proof of a theory Hi, Yael, Thanks for your question. The way to formulate the theorem of connecting the Fibonacci numbers and Pascal's theorem you attribute to Lucas is correct, and I think useful as well. The only thing is that the n/2 would better be floor(n/2), where floor(p) is the largest integer smaller than p. The formula on Ron Knott's pages uses the extra assumption that if n<k then (n,k)=0; with that assumption his formulae are correct as well. For the proof I think it would be good to use mathematical induction. You show that f(1) = f(2)=1 with your formula, and that f(n+2) = f(n+1)+f(n). Perhaps the easiest way to prove this last step is to distinguish even and odd n. It think it is a good idea to use the formula: (n,r) + (n,r+1) = (n+1,r+1) I hope this puts you on track. If you have more questions, just write back. Best regards, - Doctor Floor, The Math Forum http://mathforum.org/dr.math/ Date: 03/06/2002 at 18:52:20 From: Yael Subject: Proof of a theory Dear Dr. Floor, As you say: f(n+2) = f(n+1)+f(n) So, sum_{k=0}^{floor((n+2)/2)} {n+1-k,k} = sum_{k=0}^{floor((n+1)/2)} {n-k,k} + sum_{k=0}^{floor(n/2)} {n-1-k,k}(*) [with floor meaning in your sense largest integer smaller than p] I have tried to work on this for an hour, but can't seem to get to something useful. I know you said it is a good idea to use the formula (n,r) + (n,r+1) = (n+1,r+1) but I didn't get that at all...sorry... I mean if you plug in numbers, I saw all right that this formula is true, but I didn't get the connection to the other formula we had (the sum one)... Please could you help me with solving this -->(*). You said one should separate it into even and odd, so could you at least do it for even n's, please? Thank you so much for taking time to help me out. Yael Date: 03/07/2002 at 03:08:27 From: Doctor Floor Subject: Re: proof of a theory Hi, Yael, Thanks for your reaction. First, for the formula (n,r) + (n,r+1) = (n+1,r+1) [**], where we still assume that (n,r) = n C r, see the Dr. Math archives at Binomial Theorem by Induction http://mathforum.org/dr.math/problems/turner.7.14.96.html This is also just the addition rule for Pascal's triangle (each entry is the sum of the two entries above it). Then, you gave the formula to prove sum_{k=0}^{floor((n+2)/2)} (n+1-k,k) = sum_{k=0}^{floor((n+1)/2)} (n-k,k) + sum_{k=0}^{floor(n/2)} (n-1-k,k). This needs a little adjustment according to the formula you gave, and it seems correct, fib(n) = sum_{k=0}^{floor((n-1)/2)} {n-1-k,k}. Your formula (*) should thus be sum_{k=0}^{floor((n+1)/2)} (n+1-k,k) = sum_{k=0}^{floor(n/2)} (n-k,k) + sum_{k=0}^{floor((n-1)/2)} (n-1-k,k). Using formula [**] we will prove this identity. Case 1, n = even: When n is even, then floor((n+1)/2) = floor(n/2) = n/2 and floor((n-1)/2) = n/2-1. Hence we have sum_{k=0}^{floor(n/2)} (n-k,k) + sum_{k=0}^{floor((n-1)/2} (n-1-k,k) = sum_{k=0}^{n/2} (n-k,k) + sum_{k=0}^{n/2-1} (n-1-k,k) = <substitute k' = k+1 in the second sum> sum_{k=0}^{n/2} (n-k,k) + sum_{k'=1}^{n/2} (n-k',k'-1) = (n,0) + sum_{k=1}^{n/2} (n-k,k) + sum_{k'=1}^{n/2} (n-k',k'-1) = 1 + sum_{k=1}^{n/2} [(n-k,k) + (n-k,k-1)] = <use formula [**]> (n+1,0) + sum_{k=1}^{n/2} (n-k+1,k) = sum_{k=0}^{n/2} (n-k+1,k) as desired. Case 2, n = odd: When n is odd, then floor((n-1)/2) = floor(n/2) = (n-1)/2 and floor((n+1)/2) = (n+1)/2. Hence we have sum_{k=0}^{floor(n/2)} (n-k,k) + sum_{k=0}^{floor((n-1)/2} (n-1-k,k) = sum_{k=0}^{(n-1)/2} (n-k,k) + sum_{k=0}^{(n-1)/2-1} (n-1-k,k) = <substitute k' = k+1 in the second sum> sum_{k=0}^{(n-1)/2} (n-k,k) + sum_{k'=1}^{(n+1)/2} (n-k',k'-1) = (n,0) + sum_{k=1}^{(n-1)/2} (n-k,k) + ((n-1)/2,(n-1)/2) + sum_{k'=1}^{(n-1)/2} (n-k',k'-1) = 2 + sum_{k=1}^{(n-1)/2} [(n-k,k) + (n-k,k-1)] = <use formula [**]> (n+1,0) +((n+1)/2,(n+1)/2) + sum_{k=1}^{(n-1)/2} (n-k+1,k) = sum_{k=0}^{(n+1)/2} (n-k+1,k) as desired. I hope this helped you out. Best regards, - Doctor Floor, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/