Solutions to Problem Set 14

Math 310-01/02

10-13-2017

1. Use induction to prove that

$$5^n \ge 4^n + 2 \quad\hbox{for all}\quad n \ge 2.$$

For $n = 2$ ,

$$5^n = 25 \quad\hbox{and}\quad 4^n + 2 = 18.$$

The result is true for $n = 2$ .

Suppose that $n \ge 2$ and that the result holds for n:

$$5^n \ge 4^n + 2.$$

I must prove it for $n + 1$ . Using the induction hypothesis, I have

$$\matrix{5^{n+1} & = & 5 \cdot 5^n & \cr & \ge & 5(4^n + 2) & \hbox{(Induction hypothesis)} \cr & = & 5 \cdot 4^n + 10 & \cr & > & 4 \cdot 4^n + 10 & \hbox{(Since $5 > 4$)} \cr & = & 4^{n+1} + 10 & \cr & > & 4^{n+1} + 2 & \hbox{(Since $10 > 2$)} \cr}$$

This proves the result for $n +
   1$ , so the result holds for all $n \ge 2$ , by induction.


The Fibonacci numbers are defined by

$$f_0 = 1, \quad f_1 = 1,$$

$$f_n = f_{n - 1} + f_{n - 2} \quad\hbox{for}\quad n \ge 2.$$

2. Prove that

$$f_1 + f_3 + \cdots + f_{2 n - 1} = f_{2 n} - 1 \quad\hbox{for}\quad n \ge 1.$$

I'll use induction.

For $n = 1$ , I have $f_1 =
   1$ and $f_2 - 1 = 2 - 1 = 1$ . The result is true for $n = 1$ .

Assume that the result is true for n:

$$f_1 + f_3 + \cdots + f_{2 n - 1} = f_{2 n} - 1.$$

Then

$$f_1 + f_3 + \cdots + f_{2 n - 1} + f_{2 n + 1} = (f_{2 n} - 1) + f_{2 n + 1} = f_{2 n + 2} - 1.$$

This proves the result for $n +
   1$ , so the result is true for all $n \ge 1$ by induction.


Real stories, in distinction from those we invent, have no author. - Hannah Arendt


Contact information

Bruce Ikenaga's Home Page

Copyright 2017 by Bruce Ikenaga