4

I have two equations that I have been trying to prove. The first of which is:

F(n + 3) = 2F(n + 1) + F(n) for n ≥ 1.

For this equation the answer is in the back of my book and the proof is as follows:

1) n = 1: F(4) = 2F(2) + F(1) or 3 = 2(1) + 1, true.
2) n = 2: F(5) = 2F(3) + F(2) or 5 = 2(2) + 1, true.
3) Assume for all r, 1 ≤ r ≤ k: F(r + 3) = 2F(r + 1) + F(r)
4) Then F(k + 4) = F(k + 2) + F(k + 3) =
5) 2F(k) + F(k - 1) + 2F(k + 1) + F(k) =
6) 2[F(k) + F(k + 1)] + [F(k - 1) + F(k)] =
7) 2F(k + 2) + F(k + 1)

My first question here is how do I know how many values of n to test for? Here they chose two.

My next question is how did they get from line 3 to line 4? I understand how the statement is correct but why is this chosen? I also understand that I need to prove it's true for all values of r because if I do that it implies that it is true for k + 1. Is it just to find a relation to F(r + 3) on line 3? If that was the case why not just have F(k + 3) = F(k + 2) + F(k + 1)?

My final question about this is how did they get from line 4 to 5?

The second equation I want to prove is:

F(n + 6) = 4F(n + 3) + F(n) for n ≥ 1

I'm able to prove n = 1 and n = 2 is true but I get stuck on going from what would be line 3 - 4 on this problem. As this is my problem for homework the answer is not in the back of the book.

Now that I've gotten the help I just want to update this with the proof for my second equation (I haven't gotten the formatting down yet so bear with me):

F(n + 6) = 4F(n + 3) + F(n)
1) n = 1: F(7) = 4F(4) + F(1) or 13 = 12 + 1, true.
2) n = 2: F(8) = 4F(5) + F(2) or 21 = 20 + 1, true.
3) Assume for all r, 1 ≤ r ≤ k: F(r + 6) = 4F(r + 3) + F(r)
4) Then F(k + 7) = 4F(k + 4) + F(k + 1) =
5) F(k + 4) + F(k + 4) + F(k + 4) + F(k + 4) + F(k + 1) =
6) F(k + 4) + F(k + 4) + F(k + 4) + F(k + 3) + F(k + 2) F(k + 1) =
7) F(k + 4) + F(k + 4) + F(k + 4) +F(k + 3) + F(k + 3) =
8) F(k + 5) + F(k + 5) + F(k + 4) =
9) F(k + 6) + F(k + 5) =
10) F(k + 7)

Lucas Jablonski
  • 43
  • 6
    Note that there’s absolutely no need for induction to prove the statement: $$F(n+3)=F(n+2)+F(n+1)=\big(F(n+1)+F(n)\big)+F(n+1)=2F(n+1)+F(n)$$ simply from the definition of the Fibonacci numbers. – Brian M. Scott Feb 16 '15 at 03:13
  • @BrianM.Scott Beat me to it. I mentioned that at the beginning of the not so necessary inductive proof :) – Daniel W. Farlow Feb 16 '15 at 03:24

4 Answers4

5

For each $n\geq 0$, let $S(n)$ denote the statement $$ S(n) : F_n+2F_{n+1}=F_{n+3}. $$ First note that $S(n)$ has a rather trivial direct proof: $$ F_{n+3} = F_{n+1}+F_{n+2} = F_{n+1}+(F_n+F_{n+1})=F_n+2F_{n+1}. $$ Thus, it is really not necessary to prove your statement by using induction, but let's do it anyway since we're on the topic.

Base step: $S(0)$ says $F_0+2F_1=F_3$, which is true since $F_0=0, F_1=1$, and $F_3=2$.

Inductive step: For some fixed $k\geq 0$, assume that $S(k)$ is true. To be shown is that $$ S(k+1) : F_{k+1}+2F_{k+2} = F_{k+4} $$ follows from $S(k)$. Note that $S(k+1)$ can be proved without the inductive hypothesis; however, to formulate the proof as an inductive proof, following sequence of equalities uses the inductive hypothesis: \begin{align} F_{k+1}+2F_{k+2} &= F_{k+1}+2(F_k+F_{k+1})\\[0.5em] &= (F_{k+1}+F_k)+(F_k+2F_{k+1})\\[0.5em] &= F_{k+2}+(F_k+2F_{k+1})\\[0.5em] &= F_{k+2}+F_{k+3}\qquad\text{by $S(k)$}\\[0.5em] &= F_{k+4}. \end{align} This completes the inductive step $S(k)\to S(k+1)$.

Thus, by mathematical induction, $S(n)$ is true for every $n\geq 0$. $\Box$

Daniel W. Farlow
  • 22,531
  • So for my second equation all I need to do is the inductive step which would be F(k + 7) = 4F(k + 4) + F(k + 1). After that it's just reorganizing the right side to end up with F(k + 6) + F(k + 5)? – Lucas Jablonski Feb 16 '15 at 03:54
1

They assume that $f(k+3) = 2f(k+1) + f(k)$, then consider $f((k+1)+3) = f(k+4)$.
Setting aside our hypothesis for a moment, we know by definition that $$f((k+1) + 3) = f(k+4) = f(k+3) + f(k+2) = f((k+1)+2) + f((k+1)+1)$$ Then, substituting what we know about $f(k+3)$: $$f((k+1) + 3) = f((k+1) + 1) + 2f(k+1) + f(k)$$ $$=f((k+1)+1) + [f(k+1) + f(k)] + f(k+1)$$ $$= 2f((k+1)+1) + f(k+1) = 2f(k+2) + f(k+1)$$

jameselmore
  • 5,207
  • Thanks! That seems to be helping. The rewriting of terms was tripping me up. Pointing out F(k + 3) = 2F(k + 1) + F(k) was useful. – Lucas Jablonski Feb 16 '15 at 03:27
1

The reason for having two initial cases is that the recurrence defining the Fibonacci numbers defines each of them in terms of the two preceding Fibonacci numbers. The proof by induction uses the defining recurrence $F(n)=F(n-1)+F(n-2)$, and you can’t apply it unless you know something about two consecutive Fibonacci numbers.

Note that induction is not necessary: the first result follows directly from the definition of the Fibonacci numbers. Specifically,

$$\begin{align*} F(n+3)&=\color{brown}{F(n+2)}+F(n+1)\\ &=\color{brown}{F(n+1)+F(n)}+F(n+1)\\ &=2F(n+1)+F(n)\;. \end{align*}$$

You can use the first result to prove the second; here again no induction is needed. Start with the righthand side:

$$\begin{align*} 4F(n+3)+F(n)&=3F(n+3)+\color{brown}{F(n+3)}+F(n)\\ &=3F(n+3)+\color{brown}{F(n+2)+F(n+1)}+F(n)\\ &=2F(n+3)+\color{blue}{F(n+3)+F(n+2)}+\color{green}{F(n+1)+F(n)}\\ &=2F(n+3)+\color{blue}{F(n+4)}+\color{green}{F(n+2)}\\ &=F(n+4)+F(n+3)+\color{brown}{F(n+3)+F(n+2)}\\ &=F(n+4)+F(n+3)+\color{brown}{F(n+4)}\\ &=2F(n+4)+F(n+3)\;. \end{align*}$$

Now apply the first result, $F(m+3)=2F(m+1)+F(m)$, with $m=n+4$.

You can also do it by induction, and again you’ll need two base cases to get the induction started. If you want to try this approach, I suggest that you model your work on the induction argument that crash gives.

Brian M. Scott
  • 616,228
  • I get that you don't need to use induction but using the 2nd principal of induction was a requirement of the problem even though I didn't note that. For a problem not using Fibonacci numbers is the number of cases you prove (i.e n=1, n=2, n=3, etc.) dependent on how long it takes you to recognize a pattern? – Lucas Jablonski Feb 16 '15 at 03:35
  • @Lucas: (Aargh!! It’s certainly not your fault, but as far as I’m concerned requiring a specific approach is almost always an indication of laziness or incompetence on the part of the person posing the problem. There’s no shortage of problems for which induction is by far the most straightforward approach.) To answer your question, it’s not a matter of recognizing a pattern: it’s simply a matter of how much you need to assume in order to make the induction step work the first time. Here the step depends on being able to write a Fibonacci number in terms of the two previous ones, so you ... – Brian M. Scott Feb 16 '15 at 03:40
  • ... need to establish two base cases just to get things going. If you were trying to use induction to prove something about a sequence defined by a recurrence $x_n=x_{n-1}+x_{n-2}+x_{n-3}$, you’d need three base cases: to get $x_n$ you need $x_{n-1},x_{n-2}$ and $x_{n-3}$. This is the case even for $x_n=x_{n-1}+x_{n-3}$: you can’t get $x_4$ without having $x_1$ and $x_3$, and you need $x_2$ to get $x_5$, so you still need $x_1,x_2$, and $x_3$ just to get the induction off the ground. – Brian M. Scott Feb 16 '15 at 03:44
  • Ah that makes perfect sense now. Thanks for the help! – Lucas Jablonski Feb 16 '15 at 03:47
  • @Lucas: You’re welcome! – Brian M. Scott Feb 16 '15 at 03:47
0

the following relation on the Fibonacci numbers is sometimes useful: (for $n \ge k \ge 0$): $$ F(n+k) = \sum_{j=0}^k \binom{k}{j}F(n-j) $$ this gives: $$ F(n+6) = \sum_{j=0}^3 \binom{3}{j}F(n+3-j) \\ = F(n+3) +\color{blue}{3F(n+2)+3F(n+1)} +F(n) \\ =4 F(n+3)+F(n) $$

David Holden
  • 18,040