Induction

On the way to the market, you exchange your cow for some magic dark chocolate espresso beans. These beans have the property that every night at midnight, each bean splits into two, effectively doubling your collection. You decide to take advantage of this and each morning (around 8am) you eat 5 beans.

1. Explain why it is true that if at noon on day $n$ you have a number of beans ending in a 5, then at…

Use induction to prove for all $n \in \N$ that $\d\sum_{k=0}^n 2^k = 2^{n+1} - 1$.

Prove that $7^n - 1$ is a multiple of 6 for all $n \in \N$.

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

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 that $2^n \lt n!$ for all $n \ge 4$. (Recall, $n! = 1\cdot 2 \cdot 3 \cdot \cdots\cdot n$.)

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.

Find the flaw in the following “proof” of the “fact” that $n \lt 100$ for every $n \in \N$.

Let $P(n)$ be the statement $n \lt 100$. We will prove $P(n)$ is true for all $n \in \N$. First we establish the base case: when $n = 0$, $P(n)$ is true, because $0 \lt 100$. Now for the inductive step, assume $P(k)$ is true. That is, $k \lt 100$. Now if $k \lt 100$, then $k$ is some number, like 80. Of course $80+1 = 81$ which is still less than 100. So $k +1 \lt 100$ as well. But this is what $P(k+1)$ claims, so we have shown tha…

What is wrong with the following “proof” of the “fact” that for all $n \in \N$, the number $n^2 + n$ is odd?

Let $P(n)$ be the statement “$n^2 + n$ is odd.” We will prove that $P(n)$ is true for all $n \in \N$. Suppose for induction that $P(k)$ is true, that is, that $k^2 + k$ is odd. Now consider the statement $P(k+1)$. Now $(k+1)^2 + (k+1) = k^2 + 2k + 1 + k + 1 = k^2 + k + 2k + 2$. By the inductive hypothesis, $k^2 + k$ is odd, and of course $2k + 2$ is even. An odd plus an even is always odd, so therefore $(k+1)^2 + (k+1)$ is odd. Therefore by…

Prove that every positive integer is either a power of 2, or can be written as the sum of distinct powers of 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$.