2
$\begingroup$

I’m pulling this question from Invitation to Discrete Mathematics by Jiri Matousek and Jaroslav Nesetril. $\def\pgr{\left(\frac{1+\sqrt{5}}{2}\right)}$

They ask in an exercise to use induction to show that for the nth term in the Fibonacci sequence, $F_n \leq \pgr^{n-1}$.

This was my solution:

Base Case: $n=0$

$F_0 = 1 \leq \pgr^{-1}$ (True)

Inductive Hypothesis: $F_n \leq \pgr^{n-1}$

Inductive Step: Proving $F_{n+1} \leq \pgr^{n}$

$F_{n+1} = F_{n} + F_{n-1}$

$F_{n} + F_{n-1}\leq \pgr^{n-1} + \pgr^{n-2}$

$F_{n} + F_{n-1}\leq \left(1+\frac{1+\sqrt{5}}{2}\right) \pgr^{n-2}$

$1+\frac{1+\sqrt{5}}{2} = \pgr^2$ (This is the golden ratio)

$F_{n} + F_{n-1} \leq \pgr^{n-2+2}$

$F_{n} + F_{n-1} \leq \pgr^{n}$

$F_{n+1} \leq \pgr^{n}$

Obviously this uses strong induction, since I have to assume that if $F_n$ has a property, $F_{n-1}$ also holds that property.

I couldn’t figure out how to do it with basic induction. Is there such a way?

$\endgroup$
4
  • 4
    $\begingroup$ Just declare that you induction hypothesis $I_n$ is « $F_n$ and $F_{n-1}$ satisfy your hypothesis »… and you’ll have turned strong induction to the usual one. $\endgroup$ Commented Oct 25, 2022 at 7:56
  • $\begingroup$ See also math.stackexchange.com/a/1538834/589 $\endgroup$ Commented Oct 25, 2022 at 9:10
  • 1
    $\begingroup$ Your base case is wrong, or you are using the wrong convention, as $\phi>1.5$ you can not have $\phi^{-1}>1$. So the claim is true with $F_0=0$, $F_1=1$. You need these two instances as base case, as you use a recursion equation of order 2. $\endgroup$ Commented Oct 25, 2022 at 9:20
  • $\begingroup$ Related: math.stackexchange.com/questions/1727747/… $\endgroup$ Commented Oct 27 at 8:54

2 Answers 2

Reset to default
4
$\begingroup$

I don't think it is a worthwhile goal to blindly avoid strong induction in favour of weak induction. Theoretically is it known the two types of induction can prove exactly the same theorems, and in this case strong induction (or rather "two-level-deep" induction) fits the problem best, so that should be what you go for.

Writing down a mathematical proof is about communication, and the induction you have chosen is the one that communicates the ideas of your proof best. I think you should let it stay that way.

$\endgroup$
1
$\begingroup$

With $F_{-1},F_0,F_1=1,0,1$, the sequences $\{F_{n-1}\}_{n\ge 0}$ and $\{F_{n}\}_{n\ge 0}$ are a solution basis for the Fibonacci recursion $$a_{n+1}=a_n+a_{n-1}.$$ This means that the general solution is $$a_n=F_{n-1}a_0+F_na_1$$ (this is where an induction proof would be required). As $a_n=\phi^n$ is a solution, this gives $$ \phi^n=F_{n-1}+\phi F_n\implies \phi^{n-2}\le F_n\le \phi^{n-1}. $$

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.