(Brian Thomas Rhea hw9) |
|||
| Line 6: | Line 6: | ||
Answer: As mentioned today in class(10/21), we are allowed to complete one full page, 8.5x11", worth of cheat sheet. This can be typed, handwritten, crayon, etc. In addition, we may use any sort of calculator. | Answer: As mentioned today in class(10/21), we are allowed to complete one full page, 8.5x11", worth of cheat sheet. This can be typed, handwritten, crayon, etc. In addition, we may use any sort of calculator. | ||
| + | |||
| + | ===Question 21=== | ||
| + | '''Let f_i be the n-th Fibonacci number: f_0=0, f_1=1, f_2=1,... Prove that f_1 + f_3 + f_5 + ... + f_(2n+1) = f_(2n+2).''' | ||
| + | |||
| + | By the sequence, we initially see f_(2n+2) = f_(2n+1) + f_(2n). Since we are asked to prove something of the form f_(2n+2) = f_(2n+1) + [blah], we will assume the objective is true, and try to iron out f_(2n) to match. So, let's expand f_(2n): f_(2n) = f_(2n-1) + f_(2n-2). So, we have f_(2n+2) = f_(2n+1) + f_(2n-1) + f_(2n-2). We begin to see a pattern -- expanding an even-numbered subscript gives us an odd-numbered subscript and another even-numbered subscript to expand later. It would seem like we would end up with something like what we are trying to prove. | ||
| + | |||
| + | How can we prove this, though? The first thought that comes to mind would just be to write a sequence of expansions out as we were doing, add a couple of dots ("..."), and toss the solution at the end. However, that's not terribly rigorous. So, let's try to use induction instead: | ||
| + | |||
| + | Base case: Let n = 0. f_2 = f_1 + f_0 = f_1 (since f_0 = 0) by the definition of Fibonacci numbers, and f_2 = f_1 by the proposed recursion. | ||
| + | |||
| + | Inductive step: Assume that for a given integer n that f_1 + f_3 + f_5 + ... + f_(2n+1) = f_(2n+2). We want to show that f_1 + f_3 + f_5 + ... + f_(2n+1) + f_(2n+3) = f_(2(n+1)+2) = f_(2n+4). f_(2n+4) = f_(2n+3) + f_(2n+2) (by the Fibonacci sequence [Remember a couple of paragraphs ago? This was our initial plan.]) = f_(2n+3) + f_(2n+1) + ... + f_5 + f_3 + f_1 (by assumption [...and this is what makes the proof mathematically rigorous instead of "here's some '...'s, you get the idea"-based]). | ||
| + | |||
| + | Thus, for all integer n ≥ 0, f_1 + f_3 + f_5 + ... + f_(2n+1) = f_(2n+2). | ||
Revision as of 17:30, 23 October 2008
The midterm is Tuesday, October 28th. Here is a list of example midterm questions.
Questions and Solutions to Sample Problems
Question: For the midterm we are allowed to complete one page with notes. Does anyone know if this must be hand written or can it be typed?
Answer: As mentioned today in class(10/21), we are allowed to complete one full page, 8.5x11", worth of cheat sheet. This can be typed, handwritten, crayon, etc. In addition, we may use any sort of calculator.
Question 21
Let f_i be the n-th Fibonacci number: f_0=0, f_1=1, f_2=1,... Prove that f_1 + f_3 + f_5 + ... + f_(2n+1) = f_(2n+2).
By the sequence, we initially see f_(2n+2) = f_(2n+1) + f_(2n). Since we are asked to prove something of the form f_(2n+2) = f_(2n+1) + [blah], we will assume the objective is true, and try to iron out f_(2n) to match. So, let's expand f_(2n): f_(2n) = f_(2n-1) + f_(2n-2). So, we have f_(2n+2) = f_(2n+1) + f_(2n-1) + f_(2n-2). We begin to see a pattern -- expanding an even-numbered subscript gives us an odd-numbered subscript and another even-numbered subscript to expand later. It would seem like we would end up with something like what we are trying to prove.
How can we prove this, though? The first thought that comes to mind would just be to write a sequence of expansions out as we were doing, add a couple of dots ("..."), and toss the solution at the end. However, that's not terribly rigorous. So, let's try to use induction instead:
Base case: Let n = 0. f_2 = f_1 + f_0 = f_1 (since f_0 = 0) by the definition of Fibonacci numbers, and f_2 = f_1 by the proposed recursion.
Inductive step: Assume that for a given integer n that f_1 + f_3 + f_5 + ... + f_(2n+1) = f_(2n+2). We want to show that f_1 + f_3 + f_5 + ... + f_(2n+1) + f_(2n+3) = f_(2(n+1)+2) = f_(2n+4). f_(2n+4) = f_(2n+3) + f_(2n+2) (by the Fibonacci sequence [Remember a couple of paragraphs ago? This was our initial plan.]) = f_(2n+3) + f_(2n+1) + ... + f_5 + f_3 + f_1 (by assumption [...and this is what makes the proof mathematically rigorous instead of "here's some '...'s, you get the idea"-based]).
Thus, for all integer n ≥ 0, f_1 + f_3 + f_5 + ... + f_(2n+1) = f_(2n+2).
