CSS 342 Induction Practice Problems Solutions
***** For your personal use only. DO NOT DISTRIBUTE. *****
(Note: ^ is used for exponentiation, best to print using new courier font,
LHS means lefthand side, RHS means righthand side)
1. Find a formula for the sum of the first n even positive integers.
Using mathematical induction, prove it is the correct answer.
n
---
Prove that \
/ 2i = n(n+1) for all n >= 1.
---
i=1
Proof: By induction on n.
Basis: Show it true for n=1, show sum from i=1 to 1 of 2i = 1(1+1).
Proof:
2i is 2 when i=1.
1(1+1) = 1*2 = 2. Thus true when n=1.
Induction Hypothesis: Assume true up through some k, that is,
k
---
\
assume / 2i = k(k+1)
---
i=1
Induction step: Show that it is true for k+1, that is, show
k+1
---
\
/ 2i = (k+1)(k+1+1) = (k+1)(k+2).
---
i=1
Proof:
k+1 k
--- ---
\ \
/ 2i = / 2i + 2(k+1) break last term out of the sum
--- ---
i=1 i=1
= k(k+1) + 2(k+1) by the induction hypothesis
= (k+1)(k+2) factor out (k+1)
Therefore, the sum of 2i from 1 to n is n(n+1) for all n >= 1.
------------------------------------------------------------------------------
2. Find a formula for 1/(1*2) + 1/(2*3) + ... + 1/(n*(n+1)).
Use mathematical induction to prove your result.
(Hint: the result is n/(n+1) )
That is, show sum as i goes from 1 to n of 1/(i(i+1)) = n/(n+1)
for all n >= 1
Proof: By induction on n.
Basis: Show it true for n=1, show sum from i=1 to 1 of 1/i(i+1) = 1/(1+1).
Proof:
LHS: when i=1, 1/i(i+1) is 1/1(1+1) = 1/1*2 = 1/2 when i=1.
RHS: 1/(1+1) = 1/1*2 = 1/2. Thus true when n=1.
Induction Hypothesis: Assume true up through some k, that is,
k
---
\
/ 1/i(i+1) = k/(k+1)
---
i=1
Induction step: Show that it is true for k+1, that is, show
k+1
---
\
/ 1/i(i+1) = (k+1)/(k+1+1) = (k+1)/(k+2).
---
i=1
Proof:
k+1 k
--- ---
\ \
/ 1/i(i+1) = / 1/i(i+1) + 1/(k+1)(k+2) break last term from sum
--- ---
i=1 i=1
= k/(k+1) + 1/(k+1)(k+2) by the induction hypothesis
k(k+2) + 1
= ---------- get common denominator
(k+1)(k+2)
k^2 + 2k + 1
= ------------ multiply out
(k+1)(k+2)
(k+1)^2
= ------------ factor
(k+1)(k+2)
(k+1)
= ------- cancel (n+1) term
(k+2)
Therefore, the sum of 1/i(i+1) from 1 to n is n/(n+1) for all n >= 1.
------------------------------------------------------------------------------
3. n
---
Prove that \
/ i(i+1)(i+2) = n(n+1)(n+2)(n+3)/4 for all n >= 1.
---
i=1
Proof: By induction on n.
Basis: Show it true for n=1, show sum from i=1 to 1 of i(i+1)(1+2)
= 1(1+1)(1+2)(1+3)/4
= 1(1+1)(1+2)(4)/4
= 1(1+1)(1+2)
Proof:
LHS: When i=1, is 1*(1+1)(1+2) = 2*3 = 6.
RHS: 1(1+1)(1+2)(1+3)/4 = 1*2*3*4/4 = 1*2*3 = 6. Thus true when n=1.
Induction Hypothesis: Assume true up through some k, that is,
k
---
\
/ i(i+1)(i+2) = k(k+1)(k+2)(k+3)/4
---
i=1
Induction step: Show that it is true for k+1, that is, show
k+1
---
\
/ i(i+1)(i+2) = (k+1)(k+2)(k+3)(k+4)/4
---
i=1
Proof:
k+1 k
--- ---
\ \
/ i(i+1)(i+2) = / i(i+1)(i+2) + (k+1)(k+2)(k+3) break out last term
--- ---
i=1 i=1
= k(k+1)(k+2)(k+3)/4 + (k+1)(k+2)(k+3) by the induction hypothesis
= k(k+1)(k+2)(k+3)/4 + 4(k+1)(k+2)(k+3)/4 get common denominator
= [k(k+1)(k+2)(k+3) + 4(k+1)(k+2)(k+3)]/4 add
= (k+1)(k+2)(k+3)[k+4]/4 factor (k+1)(k+2)(k+3) out
Therefore the sum of i from 1 to n is n(n+1)(n+2)(n+3)/4 for all n >= 1.
------------------------------------------------------------------------------
4. Show that 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6
whenever n is a positive integer.
n
---
Prove that \
/ i^2 = n(n+1)(2n+1)/6 for all n >= 1.
---
i=1
Proof: By induction on n.
Basis: Show it true for n=1, show sum from i=1 to 1 of i = 1(1+1)(2*1+1)/6.
Proof:
i^2 is 1 when i=1.
1(1+1)(2*1+1)/6 = 1*2*3/6 = 1. Thus true when n=1.
Induction Hypothesis: Assume true up through some k, that is,
k
---
\
/ i^2 = k(k+1)(2k+1)/6
---
i=1
Induction step: Show that it is true for k+1, that is, show
k+1
---
\
/ i^2 = (k+1)(k+1+1)(2*(k+1)+1)/6 = (k+1)(k+2)(2k+3)/6.
---
i=1
Proof:
k+1 k
--- ---
\ \
/ i^2 = / i^2 + (k+1)^2 break last term from sum
--- ---
i=1 i=1
= k(k+1)(2k+1)/6 + (k+1)^2 by the induction hypothesis
k(k+1)(2k+1) + 6(k+1)^2
= ----------------------- get common denominator
6
(k+1)[k(2k+1) + 6(k+1)]
= ----------------------- factor out (n+1)
6
(k+1)[2k^2 + 7k + 6]
= --------------------- multiply out and add like terms
6
(k+1)(2k+3)(k+2)
= ----------------- factor
6
Therefore the sum of i^2 from 1 to n is n(n+1)(2n+1)/6 for all n >= 1.
------------------------------------------------------------------------------
5. Show that 2^n > n^2 whenever n is an integer greater than 4.
Proof: By induction on n.
Basis: Show it true for n=5, that is, show 2^n > n^2 when n=5.
Proof:
2^n = 2^5 = 32 when n=5.
n^2 = 5^2 = 25 when n=5.
Since 32 > 25, 2^n > n^2 when n=5.
Induction hypothesis: Assume 2^k > k^2 up through some k > 4.
Induction step: Show that it is true for k+1, that is, show
2^(k+1) > (k+1)^2 .
Proof:
2^(k+1) = 2 * 2^k factor out 2 (when mult, add exponents)
> 2 * k^2 by induction hypothesis (when k>4)
> k^2 + k^2 2k^2 is the same as k^2 + k^2
> k^2 + k*k k^2 is the same as k*k
> k^2 + 4k replace k with 4, since k > 4
> k^2 + 2k + 2k since 4k = 2k + 2k
> k^2 + 2k + 1 2k > 1 since k > 4
> (k+1)^2 algebra
Therefore 2^n > n^2 for all n>4.
------------------------------------------------------------------------------
6. Prove n^2 > n+1 for all n >= 2.
Proof: By induction on n.
Basis: Show it true for n=2, that is, show n^2 > n+1 when n=2.
Proof:
n^2 = 2^2 = 4 when n=2.
n+1 = 2+1 = 3 when n=2.
Since 4 > 3, n^2 > n+1 when n=2.
Induction hypothesis: Assume k^2 > k+1 up through some k>=2.
Induction step: Show that it is true for k+1, that is, show
(k+1)^2 > k+2 .
Proof:
(k+1)^2 = k^2 + 2k + 1 algebra, multiply out
> k+1 + 2k + 1 by induction hypothesis
> 3k + 2 algebra, add terms
> k + 2 since 3k > k for all k>=2
Therefore n^2 > n+1 for all n>=2.
------------------------------------------------------------------------------
7. Prove n! > n^2 for all n >= 4. (Hint: Use that n^2 > n+1 for n >= 2).
Proof: By induction on n.
Basis: Show it true for n=4, that is, show n! > n^2 when n=4.
Proof:
n! = 4! = 24 when n=4.
n^2 = 2^2 = 16 when n=4.
Since 24 > 16, n! > n^2 when n=4.
Induction hypothesis: Assume k! > k^2 up through some k>=4.
Induction step: Show that it is true for k+1, that is, show
(k+1)! > (k+1)^2 .
Proof:
(k+1)! = k! * (k+1) factor out (k+1)
> k^2 * (k+1) by induction hypothesis
> (k+1)*(k+1) since k^2 > k+1 for all k>=2
(see last problem)
> (k+1)^2 algebra
Therefore n! > n^2 for all n>=4.
------------------------------------------------------------------------------
8. Show that any postage that is a positive integer number of cents greater
than 7 cents can be formed using just 3-cent stamps and 5-cent stamps.
Proof: By induction on n, the number of cents.
Basis: Show true for n=8, that 8 cents can be formed with 3 and 5-cent stamps.
Proof:
It is true since you can use one 3-cent stamp and one 5-cent stamp to
form 8 cents.
Induction hypothesis: Assume true for up through some k, that k cents can be
formed from only 3-cent and 5-cent stamps.
Induction step: Show if you have k+1 cents, then you can form k+1 cents only
using 3-cent and 5-cent stamps.
Proof:
This is a constructive proof showing how k+1 cents can be formed in postage.
By the induction hypothesis, k cents postage can be formed using only 3-cent
and 5-cent stamps. So either at least one 5-cent stamp is used or all
3-cent stamps are used.
If the k cents includes a 5-cent stamp, replace this with two 3-cent stamps
to replace the 5-cent and account for the extra cent (the 1 of k+1).
Otherwise, only 3-cent stamps are used and k >= 9. In this case, remove
three of the 3-cent stamps and replace them with two 5-cent stamps to obtain
k+1 cents.
Thus, n cents can be formed with only 3-cent and 5-cent stamps for all n>7.
------------------------------------------------------------------------------
9. Prove if a set S has n elements then the power set of S , P(S)
which is the set of all subsets, has 2^n elements for all n >= 0.
( P(S) is the set of all subsets. For example, if S = {a, b, c} then
P(S) = { {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }. )
Proof: By induction on n.
Basis: Let n=0, that is, S has zero elements. Show P(S) has 2^0=1 element.
Proof:
If n=0 then S is the empty set, S = {}. The only subset of the empty
set is the set containing the empty set. That is, P(S) = { {} }.
Thus the power set of S contains one element.
Induction hypothesis: If S has k elements then P(S) has 2^k elements.
Induction step: Show if S has k+1 elements, then P(S) has 2^(k+1) elements.
Proof:
S has k+1 elements. Take one element, say x, and set it aside.
The remaining set has k elements, so by the inductive hypothesis,
its power set has 2^k elements. Each of these elements (the power
set of k elements) is also a member of P(S). The only members
of P(S) not counted are all those subsets including x. All the
subsets including x can be found by taking all those subsets not
including x (2^k of them) and unioning x in with them.
Altogether there are 2^k subsets without x and 2^k subsets with x.
So there are 2^k + 2^k
= 2 * 2^k
= 2^(k+1).
Thus P(S) has 2^(n+1) elements in total for all n>=0.
Example demonstrating above argument: S = {a, b, c} .
P(S) = { {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }.
Note that this is not a proof, just a demonstration to help clarify proof.
Let x=c.
subsets without x = { {}, {a}, {b}, {a,b} } has 2^n elements
subsets with x = { {c}, {a,c}, {b,c}, {a,b,c} } has 2^n elements
Together (union), these sets = P(S), which has 2^(n+1) elements.
------------------------------------------------------------------------------
n
---
\ i n+1
10. Prove / 2 = 2 -1 for all n >= 0.
---
i=0
Proof: By induction on n.
Basis: Show it true for n=0, show sum from i=0 to 0 of 2^i is 2^(0+1)-1.
Proof:
LHS: when i=0, 2^0 = 1.
RHS: 2^(0+1)-1 = 2^1 - 1 = 2-1 = 1. Thus true when n=1.
Induction Hypothesis: Assume true up through some k, that is,
k
---
\ i k+1
/ 2 = 2 - 1
---
i=0
Induction step: Show that it is true for k+1, that is, show
k+1
---
\ i k+1+1 k+2
/ 2 = 2 -1 = 2 -1
---
i=0
Proof:
k+1 k
--- ---
\ i \ i k+1
/ 2 = / 2 + 2 break last term from sum
--- ---
i=0 i=0
k+1 k+1
= 2 - 1 + 2 by the induction hypothesis
k+1 k+1
= 2 + 2 - 1 move terms around
k+1
= 2 * 2 - 1 add
k+2
= 2 - 1 add exponents for multiplication
Therefore, it is true for all n >= 0.
------------------------------------------------------------------------------
11. From lecture -- Prove that a graph with n nodes with one edge from each
node to every other node has a total of n(n-1)/2 edges.
Proof: By induction on the number of nodes, n.
Basis: Show it true for n=0.
Proof:
A graph with no nodes has zero edges. If n=0, then n(n-1)/2 = 0(0-1)/2 = 0.
Induction Hypothesis: Assume true up through some k, that is, a graph with
k nodes with one edge from each node to every other node has a total of
k(k-1)/2 edges.
Induction step: Show that it is true for k+1, that is, show that a graph
with k+1 nodes has a total of (k+1)(k+1-1)/2 = k(k+1)/2 edges.
Proof:
Consider a graph with k nodes. By the induction hypothesis, it has
k(k-1)/2 edges. Add another node to the graph, say node x. Now the
graph has k+1 nodes. The additional edges added to the graph so that
there is one edge from each node to every other node, go from node x
to each of the original k nodes. There are k new edges added to the graph.
The total number of edges in the graph with k+1 nodes is
k(k-1)/2 the original edges from k nodes
+k new edges that go from node x to the original k nodes
So k(k-1)/2 + k
= k(k-1)/2 + 2k/2
= (k(k-1) + 2k)/2
= (k^2 - k + 2k)/2
= (k^2 + k)/2
= (k(k + 1))/2
Therefore, it is true for all n >= 0.