2

I would appreciate if somebody could help me with the following problem:

Q: Show that

$$f_1=f_2=1, f_{n+2}=f_{n+1}+f_{n}(n\in \mathbb{N})~~~~ \Rightarrow ~~~~f_1f_2+f_2f_3+f_3f_4+\cdots+f_{2n-1}f_{2n}=f_{2n}^2$$

Ross Millikan
  • 374,822
Young
  • 5,492
  • 2
    Presumably you want to prove the statement on the right of your implication arrow for all $n$. However, when you are proving a statement $P(n)$ holds for all $n\in \Bbb N$, you probably have to use induction in some form or another. Why are you trying to avoid it? – rschwieb Jun 04 '13 at 13:46
  • 4
    Every time you write ${}+\dots+{}$ you are using induction. – egreg Jun 04 '13 at 13:49
  • Precisely what is meant by "not using induction"? Does it permit one to invoke lemmas or theorems that "use induction"? – Key Ideas Jun 04 '13 at 13:59

3 Answers3

2

The key idea of the classical proof is telescopy. Push the recurrence back $\,1,\,$ so $\,f_0 = 0.\,$ Note that

$$\color{#c00}{f_{2k}^2 - f_{2k-2}^2} = (f_{2k}\!-f_{2k-2})(f_{2k}\!+f_{2k-2}) = f_{2k-1}(f_{2k}\!+f_{2k-2}) = \color{#c00}{f_{2k}f_{2k-1}\! + f_{2k-1}f_{2k-2}}$$

Summing the above from $\,k=1\,$ to $\,n,\,$ the left side telescopically cancels to $\,f_{2n}^2,\,$ yielding

$$\begin{eqnarray} f_{2n}^2 &\,=\,& \qquad \color{#c00}{f_{2n}^2} &\color{#c00}-&\color{#c00}{f_{2n-2}^2} &+&\cdots &+&\quad f_4^2 &-& f_2^2 &+&\quad f_2^2 &-& f_0^2 \\ &\,=\,& \color{#c00}{ f_{2n}f_{2n-1}} &\color{#c00}+&\color{#c00}{f_{2n-1}f_{2n-2}} &+&\cdots &+& f_4 f_3 &+& f_3 f_2 &+& f_2 f_1 &+& f_1 f_0\end{eqnarray}$$

Whether or not telescopy "uses induction" depends on how that term is defined. One could inductively prove a lemma giving the general result for telescopic sums, then invoke that lemma, and that probably is a proof "not by induction". Equivalently, one could deduce it by uniqueness of solutions of the associated linear difference equation (a recurrence reformulation of telescopy). The lemma on telescopic sum evaluation (or the equivalent uniqueness theorem) has a very obvious one-line inductive proof (search on "telescopy" to find many prior answers that discuss such).

Key Ideas
  • 4,224
1

Hint: try rewriting the sum in a clever way to show what you want. To start, consider, $f_{2n}f_{2n-1} = f_{2n}(f_{2n}-f_{2n-2})$. Then see if you can't somehow make the series telescope somehow by making a similar (generalized) substitution. Then observe that $f_{1}f_{2} = f_{2}^{2}$...

(I will note that the formal use of induction that you are used to seeing is makes this problem much easier, and in fact the hint I gave you does use induction - it just avoids the typical format you are used to seeing.)

Alex Wertheim
  • 20,278
  • 1
    But telescopy does use induction. It is one of the prototypical examples of induction. – Key Ideas Jun 04 '13 at 14:01
  • Right... I suppose that I meant to provide a method which does not use the standard "show it is true for a base case, assume it's true for $n$ and then show that implies true for $n+1$". This was my best attempt to do that, though as you and other users have pointed out, there is really no way to do this problem without invoking induction. – Alex Wertheim Jun 04 '13 at 14:05
0

EDIT: Sorry, I'm not sure if I didn't notice the full title or if it's been edited since. I would still strongly recommend you use proof by induction though unless it has been expressly forbidden.

I would strongly recommend using a proof by induction.

Show this is true when $n=1$ (should be simple)

Assume this is true for $n=k$. Now what terms do you need to add to the left hand side to make it look like the rule for $n=k+1$. Add these terms to the right hand side too. Can you now make the right hand side look like it should if the rule holds for $n=k+1$? Then you're done!

john
  • 5,633