Math 455.1  •  8 March 2009

Proof by induction: examples

Example 1: (∑_(j=1)^n)(2j - 1) = (n^2)

Prove that the formula 
	1 + 3 + 5 + ⋯ + (2n - 1) = (n^2) 
for the sum of the first n odd positive integers holds for every positive integer n. In another notation, prove that 
	(∑_(j=1)^n)(2j - 1) = (n^2)
for every positive integer n.

Proof

We use induction on n.

Base step (n = 1)

When n = 1, the sum reduces to the single term 1, and 1 = (1^2).

Inductive step

Fix a positive integer n. Assume
	1 + 3 + 5 + ⋯ + (2n - 1) = (n^2).
We want to deduce from that inductive assumption that the sum of the first n + 1 odd positive integers satisfies 1 + 3 + 5 + ⋯ + (2[n + 1] - 1) = (([n + 1])^2).

Split the sum of the first n + 1 odd positive integers into the sum of two terms—the sum of the first n odd positive integers and the remaining, (n+1)st odd positive integer:

1+3+5+⋯+(2[n+1]-1) =( 1+3+5+⋯+(2n - 1)) +  (2[n+1]-1).

By the inductive assumption, the sum in braces equals (n^2); the second term is 2n  + 1. Thus
	  1+3+5+⋯+(2[n+1]-1) = (n^2) + (2n + 1) = (((n + 1))^2),
as desired.

Example 2: (2^n)<n!

Find the least positive integer K for which (2^K)<K!. Then prove that (2^n)<n! for all n≥K.

A quick experiment finds K=4:

Table[{n,(2^n)<n!},{n,1,5}]//TableForm

So the goal is to prove that (2^n)<n! for all n≥4.

Proof.

Base step (n=4)

We have (2^4)=16 < 24=4!.

Inductive step

Fix n≥4. Assume that 
	(2^n)<n!.
We want to deduce from that assumption that (2^(n+1))<(n+1)!.

Multiply both sides of the inductive assumption by 2:
	2·(2^n)<2·n!
Now 2·(2^n)=(2^(n+1)). Since n≥4, certainly 2<n+1. Hence
	(2^(n+1))<(n+1)·n!.
But (n+1)·n=(n+1)!. Hence
	(2^(n+1))<(n+1)! .

Example 3: 3 divides (n^3)+2n

Prove that 3 divides (n^3) + 2 n for every positive integer n.

Proof

We use induction on n.

Base step (n = 1)

When n = 1, the quantity (n^3) + 2 n = 3, and certainly 3 divides 3.

Inductive step

Fix a positive integer n. Assume
	3 divides (n^3) + 2 n.
We want to deduce from that inductive assumption that 3 divides (((n + 1))^3) + 2 (n + 1).

We calculate:

(((n + 1))^3) + 2 (n + 1) = (n^3) + 3(n^2) + 3n + 1 + 2n + 2 = ((n^3) + 2n) + 3 (n^2) + 3n + 3 = ((n^3) + 2n) + 3((n^2) + n + 1).

By the inductive assumption, 3 divides the term (n^3) + 2n; certainly 3 divides the term  3((n^2) + n + 1). Hence 3 divides their sum, which is (((n + 1))^3) + 2 (n + 1).

Copyright © 2009 by Murray Eisenberg.  All rights reserved.

Example 4: Fibonacci number (Subscript[F, 3n]) is even

Prove that, for every n=1,2,…, the 3nth Fibonacci number (Subscript[F, 3n]) is even.
Recall that the Fibonacci numbers are given recursively by:
	(Subscript[F, 1])=1,
(Subscript[F, 2])=1,
(Subscript[F, n+1])=(Subscript[F, n])+(Subscript[F, n-1])          (n=1,2,…)

Proof.

Base step (n=1)

We have (Subscript[F, 3·1])=(Subscript[F, 3])=(Subscript[F, 2])+(Subscript[F, 1])=1+1=2, which is even.

Inductive step

Fix n≥1 and assume that (Subscript[F, 3n]) is even. We want to deduce from that assumption that (Subscript[F, 3(n+1)]) is even. [Note: What we want to deduce is not that (Subscript[F, 3n+1]) is even!]

We have
	(Subscript[F, 3(n+1)])=(Subscript[F, 3n+3])=(Subscript[F, 3n+2])+(Subscript[F, 3n+1])
               =(Subscript[(F, 3n+1])+(Subscript[F, 3n]))+(Subscript[F, 3n+1])
                       =(Subscript[F, 3n])+2(Subscript[F, 3n+1]).
Now (Subscript[F, 3n]) is even by the inductive assumption, and certainly 2(Subscript[F, 3n+1]) is even; hence their sum (Subscript[F, 3n])+2(Subscript[F, 3n+1]) is also even. But this sum is (Subscript[F, 3(n+1)]).