A Fibonacci Proof by InductionDate: 06/05/98 at 09:20:23 From: Michael Wang Subject: Fibonacci sequence: Proving by induction Dear Doctor Maths, I need to prove the following by induction: Let u_1, u_2, ..... be the Fibonacci sequence. Prove by induction that for n > 0: u_(n-1) + u_(n-3) + u_(n-5) + ... < u_n I am really stuck on this one because I don't even know where to begin. I am not sure how to prove that this is true for S_1 and then prove it is true for S_k and S_k+1. Your help in the matter would be most appreciated. Thank you, Michael Date: 06/05/98 at 12:19:32 From: Doctor Rob Subject: Re: Fibonacci sequence: Proving by induction You didn't tell me the values of u_1 and u_2, so I am not sure which Fibonacci sequence you mean. There are at least two different ones that are called by that name. This is important for establishing S_1. I will assume that u_1 = 1, u_2 = 2. One simple approach is to separate this into two cases, n even and n odd. First consider the case where n is odd, n = 2*k+1. Then let S_k be the statement that: u_(2*k) + u_(2*k-2) + u_(2*k-4) + ... < u_(2*k+1). Then S_1 is the statement that u_2 < u_3. That is true because u_2 = 2 and u_3 = 3. Assume S_k is true for some value of k. Then add u_(2*k) to both sides. On the right side, use the Fibonacci recursion to conclude that u_(2*k-1) + u_(2*k) = u_(2*k+1) = u(2*[k+1]-1). Then you have proven S_(k+1) by assuming S_k, so S_k implies S_(k+1). By the Principle of Mathematical Induction, S_k is true for all k, so the statement you are trying to prove is true for all odd values of n. Next consider the case where n is even, n = 2*k. Now let T_k be the statement that: u_(2*k-1) + u_(2*k-3) + u_(2*k-5) + ... < u_(2*k). Then T_1 is the statement that u_1 < u_2. That is true because u_1 = 1 and u_2 = 2. Assume T_k is true for some value of k. Then add u_(2*k+1) to both sides. On the right side, use the Fibonacci recursion to conclude that u_(2*k) + u_(2*k+1) = u_(2*k+2) = u(2*[k+1]). Then you have proven T_(k+1) by assuming T_k, so T_k implies T_(k+1). By the Principle of Mathematical Induction, T_k is true for all k, so the statement you are trying to prove is true for all even values of n. -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/ Date: 06/05/98 at 16:19:30 From: Doctor Anthony Subject: Re: Fibonacci sequence: Proving by induction For the first step: u(3) + u(1) < u(4) (yes, because u(4) = u(3) + u(2) and u(2) > u(1)) u(4) + u(2) < u(5) (yes, because u(5) = u(4) + u(3) and u(3) > u(2)) Assume it is true for n = k: u(k-1) + u(k-3) + .... < u(k) Now add u(k+1) to both sides and we have: u(k+1) + u(k-1) + u(k-3) + ... < u(k) + u(k+1) u(k+1) + u(k-1) + u(k-3) + ... < u(k+2) This is the same expression as we had before, except that k is replaced by k+2. So if the result is true for n = k it is also true for n = k+2. But it is true for n = 4, so it is true for n = 6, and if it is true for n = 6, then it is true for n = 8, 10, .... It is also true for n = 5 and so for n = 7, 9, 11, ... So the result is true for all positive integral values of n. -Doctor Anthony, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/