1. Prove that for every n >= 1,

We argue by induction. For n=1, the expression has the value . So the assertion is true for n=1.

Now assume that for some integer k, . Then there must exist an integer t such that . Now we must show that the assertion must be true for k+1, i.e. that .'

However,

So we have , and the result follows by induction.

2. Prove by induction that the sum 1 + 3 + 5 + 7 + ... + 2n-1 is a perfect square.

It is almost impossible to prove this assertion without proving much more.

For convenience, let S_n = 1 + 3 + 5 + 7 + ... + 2n-1. Then S_n+1 = S_n + (2n+1).

Now the result is easily seen to be true in the case k=1, since 1 is a perfect square.

Now assume that S_k is a perfect square, say S_k = t² for some t. Then we must show that S_k+1 is also a perfect square. Well, S_k+1 = S_k + (2k+1) = t² + 2k +1.

Now what?? Well, we seem to be stuck. The proof isn't going anywhere.

But look what happens if we try to prove the stronger result that S_n= n².

Our argument would be almost the same as before except that at the very end

we would have:

      S_k+1 = S_k + (2k+1) = k² + 2k +1 = (k+1)².

And now the induction proof works!

This is the Inventor's Paradox - it is often easier to prove a stronger result than what you need. Here we prove not just that S_n is a perfect square, but that it is a particular perfect square, namely n².

3. Let f_n be the nth Fibonacci number,
Prove by induction: For every n>=1, 2 | f_3n ( i.e. f_3n is even)

Proof.
We argue by induction. For n=1 this says that f₃ = 2 is even - which it is.

Now suppose that for some k, f_3k is even. So f_3k = 2m for some integer m.
Now we must show that f_3(k+1) is even.

Then, f_3(k+1) = f_3k+3 = f_3k+2 +f_3k+1 = f_3k+1 + f_3k + f_3k+1 = 2f_3k+1 + f_3k = 2(f_3k+1 + m ).

4. Prove by Induction: For all integers n >= 1,

Proof: For n=1 this asserts that - which is certainly true. Now suppose that for some integer k >= 1, . Thus, there is some integer m such that .

We claim that . But this is equivalent to showing that .
However, , and so is a multiple of 4 and the result follows by induction.

5. Prove by induction: For any n>=1, 7 | 8ⁿ - 1.
We argue by induction. For n=1 this just says that 7 | 7 which is true.
Now suppose that for some k>=1, 7 | 8^k - 1. So that 8^k - 1 = 7t for some integer t.
We must show that 7 | 8^k+1 - 1. But, 8^k+1 - 1 = 8 ( 8^k - 1 ) + 7 = 8(7t) + 7 = 7( 8t +1 ).
And so we have 8^k+1 - 1 is a multiple of 7 and so, 7 | 8^k+1 - 1.

A Fibonacci Series Problem

Recall that the Fibonacci numbers are defined by the recurrence relation,

f_n = f_n-1 + f_n-2 n>2, f₁=1, f₂=1.

So, f₁=1, f₂=1, f₃=2, f₄=3, f₅=5, f₆=8, f₇=13, f₈=21, f₉=34, ...

In this exercise we will determine some highly interesting properties of the Fibonacci numbers.

A. Show by induction that for all n>2.

B. Show by induction that .

C. Show (by simple algebraic manipulation) that .

D. Recall that every bounded, monotone sequence converges. Using this fact, prove:

Lemma. If a_n is a bounded sequence in which

(i). a₃ > a₅ > a₇ > ...

(ii). a₂ < a₄ < a₆ < ...

(iii). lim |a_n+1-a_n|=0

Then a_n converges.

E. Show that satisfies the conditions of the lemma in (D). Consequently, we know that the sequence must converge to some limit t.

Problem: Find the exact value of t. Note that by (A) your answer should be a number somewhere between 1 and 2.

F. Using the result of (E), determine if the power series converges or diverges.

More Induction Exercises

1. Show that n lines in general position divide the plane into regions.

2. If every two cities in state A are joined by a one-way road,then it is possible to find a starting city A and a route from A that passes through every city exactly once.

3. 5^2n-1 + 1 is divisible by 6.

4. xⁿ-yⁿ is divisible by x-y. (Hint: you need to "expose" the inductive hypothesis (that xⁿ-yⁿ is divisible by x-y). Suggestion: add and subtract xyⁿ to xⁿ⁺¹ - yⁿ⁺¹)

5. n² + n + 41 is prime for n=1,2...40, but it is not prime for all n >= 1.

6. For every integer n >= 1, holds for any collection of n sets. A₁, A₂, ..., A_n.

7. For every integer n >= 1, is divisible by at least n distinct primes.

8. Show that if x is the root of 1- x - x² so that x²= 1 - x, then for every integer n >= 1,
x²ⁿ = f_2n-1 - xf_2n.

                        Example Induction Argument

1. Prove by induction: For all n >= 1, 9ⁿ -1 is divisible by 8.

We will argue by induction⁽¹⁾. We first note that for n=1, this just says that 8 | 8 which is clearly true.

Now, assume that the result holds for some⁽²⁾ integer k. So, 8 | 9^k -1, and hence
9^k -1 = 8t for some integer t.

We claim that the result is true for the next larger integer, k+1. That is, we claim that

8 | 9^k+1 -1. Once we show this we will be finished.

But, 9^k+1 -1 = 9( 9^k -1 ) + 8 = 9( 8t ) + 8 = 8( 9t +1 ) and so 9^k+1 -1 is a multiple of 8, and so 8 | 9^k+1 -1. Thus our result follows by induction.⁽³⁾

=========================

1. This is just to let everybody know what we are up to so they will know what to expect in the forthcoming argument.

2. Don't say, "assume that the result holds for all n," or anything equivalent to it. That's what you are trying to prove. The word some is significant here.

3. In the algebra at the end don't write:

            8 | 9^k+1 - 1 = 9( 9^k -1 ) + 8

The left-hand side of this expression is an assertion,

"8 divides 9^k+1 - 1, " while the right-hand side is an algebraic expression.

Similarly, don't write

            8 | 9^k+1 - 1 9( 9^k -1 ) + 8

Either of the following is fine:

      9^k+1 - 1 = 9( 9^k -1 ) + 8 (Both sides are algebraic expressions.)

                              OR

      8 | 9^k+1 - 1 8 | 9( 9^k -1 ) + 8 (Both sides are equivalent assertions.)

Induction Problems

1. Prove that for every n >= 1,

2. An integer n is a perfect square if it is the square of some other integer.

(For example 1, 4, 9, 16, 25 and 36 are all perfect squares.) Prove by induction that the sum 1 + 3 + 5 + 7 + ... + 2n-1 (i.e. the sum of the first n odd integers) is always a perfect square.

3. Show that any 2ⁿ x 2ⁿ board with one square deleted can be covered by Triominoes.