Mathematical Induction

Prove that $1 + 3 + 5 + \cdots + (2n-1) = n^2$ for all $n \ge 1$.

Prove that $2^n \lt n!$ for all $n \ge 4$. (Recall, $n! = 1\cdot 2 \cdot 3 \cdot \cdots\cdot n$.)

Prove that the sum of $n$ squares can be found as follows

What is wrong with the following “proof” of the “fact” that $n+3 = n+7$ for all values of $n$ (besides of course that the thing it is claiming to prove is false)?

Let $P(n)$ be the statement that $n + 3 = n + 7$. We will prove that $P(n)$ is true for all $n \in \N$. Assume, for induction that $P(k)$ is true. That is, $k+3 = k+7$. We must show that $P(k+1)$ is true. Now since $k + 3 = k + 7$, add 1 to both sides. This gives $k + 3 + 1 = k + 7 + 1$. Regrouping $(k+1) + 3 = (k+1) + 7$. But this is simply $P(k+1)$. Thus by the prin…

The proof in the previous problem does not work. But if we modify the “fact,” we can get a working proof. Prove that $n + 3 \lt n + 7$ for all values of $n \in \N$. You can do this proof with algebra (without induction), but the goal of this exercise is to write out a valid induction proof.

Now give a valid proof (by induction, even though you might be able to do so without using induction) of the statement, “for all $n \in \N$, the number $n^2 + n$ is even.”

Use induction to prove that if $n$ people all shake hands with each other, that the total number of handshakes is $\frac{n(n-1)}{2}$.

Use the product rule for logarithms ($\log(ab) = \log(a) + \log(b)$) to prove, by induction on $n$, that $\log(a^n) = n \log(a)$, for all natural numbers $n \ge 2$.

Prove that $F_0 + F_2 + F_4 + \cdots + F_{2n} = F_{2n+1} - 1$ where $F_n$ is the $n$th Fibonacci number.

Prove, using strong induction, that every natural number is either a Fibonacci number or can be written as the sum of distinct Fibonacci numbers.

Prove, by mathematical induction, that $F_1 + F_3 + F_5 + \dots + F_{2n -1} = F_{2n}$, where $F_n$ is the $n$th Fibonacci number.

Prove that 6 divides $7^n - 1$ for all $n \in \N$.