6.042/18.062J Mathematics for Computer Science February 8,2005
Srini Devadas and Eric Lehman
Problem Set 2 Solutions
Due,Monday,February 14 at 9 PM
Problem 1,Use induction to prove that
1 1 1 1 1
=1? 1? 1? 1?
2 3 4
···
n n
for all n ≥ 2,
Solution,The proof is by induction on n,Let P(n) be the proposition that the equation
above holds,
Base case,P(2) is true because
1 1
=1?
2 2
Inductive step,Assume P(n) is true,Then we can prove P(n + 1) is also true as follows,
1 1 1 1 1 1
= 1?1? 1? 1? 1?
2 3
···
n n + 1 n
·
n + 1
1
=
n + 1
The?rst step uses the assumption P(n) and the second is simpli?cation,
Thus,P(2) is true and P(n) implies P(n + 1) for all n ≥ 2,Therefore,P(n) is true for
all n ≥ 2 by the principle of induction,
Problem 2,DeMorgan’s Law for sets says,
A∩(B ∪C) = (A∩B)∪(A∩C)
Assume this and prove this extension of DeMorgan’s Law to n ≥ 2 sets,
A∩(B
1
∪B
2
∪...∪B
n
) = (A∩B
1
)∪(A∩B
2
)∪...∪(A∩B
n
)
Extending formulas to an arbitrary number of terms is a common (if mundane) applica-
tion of induction,
2 Problem Set 2
Solution,We use induction,Let P(n) be the proposition that
A∩ (B
1
∪ B
2
∪,..∪ B
n
) = (A∩ B
1
)∪ (A∩ B
2
)∪,..∪ (A∩ B
n
)
for all sets A and B
1
,...,B
n
,
Base case,P(2) follows from DeMorgan’s original law with B = B
1
and C = B
2
,
Inductive step,Assuming P(n),we can deduce P(n + 1) as follows,
A∩ (B
1
∪ B
2
∪ B
3
∪,..∪ B
n
) = A∩ ((B
1
∪ B
2
)∪ B
3
∪,..∪ B
n
)
= (A∩ (B
1
∪ B
2
)) ∪ (A∩ B
3
)∪,..∪ (A∩ B
n
)
= (A∩ B
1
)∪ (A∩ B
2
)) ∪ (A∩ B
3
)∪,..∪ (A∩ B
n
)
In the?rst step,we group B
1
and B
2
,This allows us to apply the assumption P(n) in the
second step,The last step uses DeMorgan’s original law,
Since P(2) is true and P(n)? P(n+ 1) for all n ≥ 2,the principle of induction implies
that P(n) is true for all n ≥ 2,
Problem 3,Let H
n
denote the n-th harmonic sum,which is de?ned by,
n
1
H
n
=
k
k=1
Harmonic sums come up often,You’ll see them again later in 6.042 and also in 6.046,
Claim,H
2
m ≥ 1 + m/2 for all m ≥ 0,
(a) The next problem part will ask you to prove this claim by induction,To make this
easier,three steps that you may?nd useful in your proof are listed below,Provide
a one sentence justi?cation for each of these steps,
2
m+1
1
H
2
m+1 =
k
k=1
2
m+1
1
= H
2
m +
k
k=2
m
+1
1
≥ H
2
m + 2
m
2
m+1
·
Solution,The?rst step uses the de?nition of H
2
m+1, The second step uses the fact
that the?rst 2
m
terms of the sum are equal to all 2
m
terms of H
2
m, The third step
uses the fact that a sum is lower bounded by the number of terms times the smallest
term,
3 Problem Set 2
(b) Prove the claim by induction,(See? We told you this was going to happen.,, )
Solution,We prove the claim by induction,Let P(m) be the proposition that H
2
m ≥
1 + m/2,
Base case,Note that P(0) is true,because,
H
2
0 = H
1
= 1 ≥ 1 + 0/2
Inductive step,We must show that P(m) implies P(m + 1) for all m ≥ 0,We assume
that P(m) is true and reason as follows,
2
m+1
1
H
2
m+1 =
k
k=1
2
m+1
1
= H
2
m +
k
k=2
m
+1
1
H
2
m + 2
m
m+1
≥ ·
2
(1 + m/2) + 1/2≥
= 1 + (m + 1)/2
The?rst step uses the de?nition of H
2
m+1, The second step uses the fact that the?rst
2
m
terms of the sum are equal to all 2
m
terms of H
2
m, The third step uses the fact that
a sum is lower bounded by the number of terms times the smallest term,The fourth
step uses our assumption P(m) and simpli?cation,The last step uses only algebra,
This shows that P(m + 1) is true,and so P(m) is true for all m ≥ 0 by induction,
(c) Show that this implies H
n
≥ 1 +
1
2
log
2
n when n is a power of 2,
Solution,This inequality follows from substituting n = log
2
m into the claim,
Problem 4,Suppose we want to divide a class of n students into groups each containing
either 4 or 5 students,
(a) Let’s try to use strong induction to prove that a class with n ≥ 8 students can be
divided into groups of 4 or 5,
Proof,The proof is by strong induction,Let P(n) be the proposition that a class with
n students can be divided into teams of 4 or 5,
Base case,We prove that P(n) is true for n = 8,9,or 10 by showing how to break
classes of these sizes into groups of 4 or 5 students,
8 = 4 + 4
9 = 4 + 5
10 = 5 + 5
4 Problem Set 2
Inductive step,We must show that P(8),...,P(n) imply P(n+1) for all n ≥ 10,Thus,
we assume that P(8),...,P(n) are all true and show how to divide up a class of n+1
students into groups of 4 or 5,We?rst form one group of 4 students,Then we can
divide the remaining n?3 students into groups of 4 or 5 by the assumption P(n?3),
This proves P(n + 1),and so the claim holds by induction,
This proof contains a critical logical error,Identify the?rst sentence in the proof that
does not follow and explain what went wrong,(Pointing out that the claim is false
is not suf?cient; you must?nd the?rst logical error in the proof.)
Solution,The?rst error is in the sentence,
Then we can divide the remaining n? 3 students into groups of 4 or 5 by
the assumption P(n? 3),
If n = 10,then P(n?3) = P(7),which is not among our assumptions P(8),...,P(n),
In this case,P(n + 1) = P(11) is actually false,
(b) Provide a correct strong induction proof that a class with n ≥ 12 students can be
divided into groups of 4 or 5,
Solution,The proof is by strong induction,Let P(n) be the proposition that a class
with n students can be divided into teams of 4 or 5,
Base case,We prove that P(n) is true for n = 12,13,14,and 15 by showing how to
break classes of these sizes into groups of 4 or 5 students,
12 = 4 + 4 + 4
13 = 4 + 4 + 5
14 = 4 + 5 + 5
15 = 5 + 5 + 5
Inductive step,We must show that P(12),...,P(n) imply P(n + 1) for all n ≥ 15,
Thus,we assume that P(12),...,P(n) are all true and show how to divide up a
class of n + 1 students,We?rst form one group of 4 students,Then we can divide
the remaining n? 3 students into groups of 4 or 5 by the assumption P(n? 3),
(Note that n ≥ 15 and so n? 3 ≥ 12; thus,P(n? 3) is among our assumptions
P(12),...,P(n).) This proves P(n + 1),and so the claim holds by induction,
Problem 5,
Claim,If a collection of positive integers (not necessarily distinct) has sum n ≥ 1,then the
collection has product at most 3
n/3
,
For example,the collection 2,2,3,4,4,7 has the sum,
5 Problem Set 2
2 + 2 + 3 + 4 + 4 + 7 = 22
On the other hand,the product is,
2 2 3 4 4 7 = 1344 · · · · ·
≤ 3
22/3
3154.2≈
(a) As a preliminary step,use strong induction to prove that n ≤ 3
n/3
for every inte-
ger n ≥ 0.
Solution,The proof is by strong induction,Let P(n) be the proposition that n ≤
3
n/3
.
Base case,We show that P(0),P(1),P(2),P(3),and P(4) are true:
0
3
≤ 3
0
→ 0 ≤ 3
0/3
1
3
≤ 3
1
→ 1 ≤ 3
1/3
2
3
≤ 3
2
→ 2 ≤ 3
2/3
3
3
≤ 3
3
→ 3 ≤ 3
3/3
4
3
≤ 3
4
→ 4 ≤ 3
4/3
Each implication follows by taking cube roots,
Inductive step,Now,we show that P(0),...,P(n) imply P(n+ 1) for all n ≥ 4,Thus,
we assume that P(0),...,P(n) are all true and reason as follows,
3
(n+1)/3
= 3 3
(n?2)/3
·
3 · (n? 2)≥
n + 1 (for all n ≥ 7/2)≥
The?rst step is algebra,The second step uses our assumption P(n? 2),The third
step is a linear inequality that holds for all n ≥ 7/2,(This forced us to deal individ-
ually with the cases P(3) and P(4),above.) Therefore,P(n + 1) is true,and so P(n)
is true for all n ≥ 0 by induction,
(b) Prove the claim using induction or strong induction,(You may?nd it easier to
use induction on the number of positive integers in the collection rather than induction
on the sum n.)
Solution,We use induction on the size of the collection,Let P(k) be the proposition
that every collection of k positive integers with sum n has product at most 3
n/3
,
First,note that P(1) is true by the preceding problem part,
6 Problem Set 2
Next,we must show that P(k) implies P(k + 1) for all k ≥ 1,So assume that P(k)
is true,and let x
1
,...,x
k+1
be a collection of positive integers with sum n,Then we
can reason as follows,
x
1
x
2
···x
k
·x
k+1
≤ 3
(n?x
k+1
)/3
·x
k+1
·
≤ 3
(n?x
k+1
)/3
3
x
k+1
/3
·
= 3
n/3
The?rst step uses the assumption P(k),the second uses the preceding problem part,
and the last step is algebra,This shows that P(k + 1) is true,and so the claim holds
by induction,
Problem 6,Suppose that you take a piece of paper and draw n straight lines,no one
exactly on top of another,that completely cross the paper,This divides the paper into
polygonal regions,Prove by induction that you can color each region either red or blue
so that two regions that share a boundary are always colored differently,(Regions that
share only a boundary point may have the same color.)
Solution,The proof is by induction,Let P(n) be the proposition that the regions
de?ned by n lines can be colored red or blue so that adjacent regions are different colors,
Base case,If n = 0,then there are no lines and the whole paper is a single region,Color
it red,Adjacent regions are different colors trivially since there are no adjacent regions,
Thus,P(0) is true,
Inductive step,Assume that P(n) is true,We prove that P(n + 1) is also true,Given
a con?guration of n + 1 lines,remove an arbitrary line l,By the assumption P(n),the
polygonal regions de?ned by the remaining n lines can be colored red or blue so that
adjacent regions are colored differently,Now add back the line l and invert the color of
every region to one side of l,Adjacent regions on the same side of the line are different
colors by the induction assumption P(n),Adjacent region on opposite sides of the line
are different colors because the colors on one side were inverted,Therefore,P(n) implies
P(n + 1),and so P(n) is true for all n ≥ 0 by induction,
Problem 7,Let’s consider a variation of the Unstacking game demonstrated in lecture,As
before,the player is presented with a stack of n ≥ 1 bricks,Through a sequence of moves,
she must reduce this to n single-brick stacks while scoring as many points as possible,A
move consists of dividing a single stack of (a + b) bricks (where a,b > 0) into two stacks
with heights a and b,Suppose that this move is worth a+ b points,Find the best strategy
and use induction to prove that there is no better strategy,
Solution,Some experimentation suggests that the best strategy is to remove one block
Problem Set 2 7
at a time,This gives a score of,
n(n + 1)
n + (n? 1) +,.,+ 3 + 2 =? 1
2
(n + 2)(n? 1)
=
2
Now we must prove that there is no better strategy,
Proof,We use strong induction,Let P(n) be the proposition that unstacking n bricks is
worth at most (n + 2)(n? 1)/2 points,
Base case,P(1) is true because the game ends immediately when there is only 1 brick,
Thus,the player’s score is 0,which is the value of (n + 2)(n? 1)/2 when n = 1,
Inductive step,Now assume that P(1),...,P(n? 1) are all true in order to prove P(n),
where n ≥ 2,Suppose the stack of n bricks is split into stacks of height x and n? x,where
0 < x < n,The player’s best possible score for the game is then,
((n? x) + x)+ (x + 2)(x? 1)/2+(n? x + 2)(n? x? 1)/2
for?rst move to unstack x bricks to unstack n? x bricks
Here we are using the assumptions P(x) and P(n? x),which specify the best possible
scores for unstacking x and n? x bricks,Now we must choose x to maximize this expres-
sion,The derivative with respect to x is 2x? n,Thus,the expression decreases as x grows
from 1 to n/2 and then increases symmetrically as x grows
from n/2 to n? 1,Therefore,the maximum is achieved when x = 1 or x = n? 1,In
both cases,the expression above is equal to,
(n + 2)(n? 1)
2
So we have shown that P(1),.,,,P(n? 1) imply P(n),
Therefore,P(n) is true for all n ≥ 1 by the strong induction principle,
Srini Devadas and Eric Lehman
Problem Set 2 Solutions
Due,Monday,February 14 at 9 PM
Problem 1,Use induction to prove that
1 1 1 1 1
=1? 1? 1? 1?
2 3 4
···
n n
for all n ≥ 2,
Solution,The proof is by induction on n,Let P(n) be the proposition that the equation
above holds,
Base case,P(2) is true because
1 1
=1?
2 2
Inductive step,Assume P(n) is true,Then we can prove P(n + 1) is also true as follows,
1 1 1 1 1 1
= 1?1? 1? 1? 1?
2 3
···
n n + 1 n
·
n + 1
1
=
n + 1
The?rst step uses the assumption P(n) and the second is simpli?cation,
Thus,P(2) is true and P(n) implies P(n + 1) for all n ≥ 2,Therefore,P(n) is true for
all n ≥ 2 by the principle of induction,
Problem 2,DeMorgan’s Law for sets says,
A∩(B ∪C) = (A∩B)∪(A∩C)
Assume this and prove this extension of DeMorgan’s Law to n ≥ 2 sets,
A∩(B
1
∪B
2
∪...∪B
n
) = (A∩B
1
)∪(A∩B
2
)∪...∪(A∩B
n
)
Extending formulas to an arbitrary number of terms is a common (if mundane) applica-
tion of induction,
2 Problem Set 2
Solution,We use induction,Let P(n) be the proposition that
A∩ (B
1
∪ B
2
∪,..∪ B
n
) = (A∩ B
1
)∪ (A∩ B
2
)∪,..∪ (A∩ B
n
)
for all sets A and B
1
,...,B
n
,
Base case,P(2) follows from DeMorgan’s original law with B = B
1
and C = B
2
,
Inductive step,Assuming P(n),we can deduce P(n + 1) as follows,
A∩ (B
1
∪ B
2
∪ B
3
∪,..∪ B
n
) = A∩ ((B
1
∪ B
2
)∪ B
3
∪,..∪ B
n
)
= (A∩ (B
1
∪ B
2
)) ∪ (A∩ B
3
)∪,..∪ (A∩ B
n
)
= (A∩ B
1
)∪ (A∩ B
2
)) ∪ (A∩ B
3
)∪,..∪ (A∩ B
n
)
In the?rst step,we group B
1
and B
2
,This allows us to apply the assumption P(n) in the
second step,The last step uses DeMorgan’s original law,
Since P(2) is true and P(n)? P(n+ 1) for all n ≥ 2,the principle of induction implies
that P(n) is true for all n ≥ 2,
Problem 3,Let H
n
denote the n-th harmonic sum,which is de?ned by,
n
1
H
n
=
k
k=1
Harmonic sums come up often,You’ll see them again later in 6.042 and also in 6.046,
Claim,H
2
m ≥ 1 + m/2 for all m ≥ 0,
(a) The next problem part will ask you to prove this claim by induction,To make this
easier,three steps that you may?nd useful in your proof are listed below,Provide
a one sentence justi?cation for each of these steps,
2
m+1
1
H
2
m+1 =
k
k=1
2
m+1
1
= H
2
m +
k
k=2
m
+1
1
≥ H
2
m + 2
m
2
m+1
·
Solution,The?rst step uses the de?nition of H
2
m+1, The second step uses the fact
that the?rst 2
m
terms of the sum are equal to all 2
m
terms of H
2
m, The third step
uses the fact that a sum is lower bounded by the number of terms times the smallest
term,
3 Problem Set 2
(b) Prove the claim by induction,(See? We told you this was going to happen.,, )
Solution,We prove the claim by induction,Let P(m) be the proposition that H
2
m ≥
1 + m/2,
Base case,Note that P(0) is true,because,
H
2
0 = H
1
= 1 ≥ 1 + 0/2
Inductive step,We must show that P(m) implies P(m + 1) for all m ≥ 0,We assume
that P(m) is true and reason as follows,
2
m+1
1
H
2
m+1 =
k
k=1
2
m+1
1
= H
2
m +
k
k=2
m
+1
1
H
2
m + 2
m
m+1
≥ ·
2
(1 + m/2) + 1/2≥
= 1 + (m + 1)/2
The?rst step uses the de?nition of H
2
m+1, The second step uses the fact that the?rst
2
m
terms of the sum are equal to all 2
m
terms of H
2
m, The third step uses the fact that
a sum is lower bounded by the number of terms times the smallest term,The fourth
step uses our assumption P(m) and simpli?cation,The last step uses only algebra,
This shows that P(m + 1) is true,and so P(m) is true for all m ≥ 0 by induction,
(c) Show that this implies H
n
≥ 1 +
1
2
log
2
n when n is a power of 2,
Solution,This inequality follows from substituting n = log
2
m into the claim,
Problem 4,Suppose we want to divide a class of n students into groups each containing
either 4 or 5 students,
(a) Let’s try to use strong induction to prove that a class with n ≥ 8 students can be
divided into groups of 4 or 5,
Proof,The proof is by strong induction,Let P(n) be the proposition that a class with
n students can be divided into teams of 4 or 5,
Base case,We prove that P(n) is true for n = 8,9,or 10 by showing how to break
classes of these sizes into groups of 4 or 5 students,
8 = 4 + 4
9 = 4 + 5
10 = 5 + 5
4 Problem Set 2
Inductive step,We must show that P(8),...,P(n) imply P(n+1) for all n ≥ 10,Thus,
we assume that P(8),...,P(n) are all true and show how to divide up a class of n+1
students into groups of 4 or 5,We?rst form one group of 4 students,Then we can
divide the remaining n?3 students into groups of 4 or 5 by the assumption P(n?3),
This proves P(n + 1),and so the claim holds by induction,
This proof contains a critical logical error,Identify the?rst sentence in the proof that
does not follow and explain what went wrong,(Pointing out that the claim is false
is not suf?cient; you must?nd the?rst logical error in the proof.)
Solution,The?rst error is in the sentence,
Then we can divide the remaining n? 3 students into groups of 4 or 5 by
the assumption P(n? 3),
If n = 10,then P(n?3) = P(7),which is not among our assumptions P(8),...,P(n),
In this case,P(n + 1) = P(11) is actually false,
(b) Provide a correct strong induction proof that a class with n ≥ 12 students can be
divided into groups of 4 or 5,
Solution,The proof is by strong induction,Let P(n) be the proposition that a class
with n students can be divided into teams of 4 or 5,
Base case,We prove that P(n) is true for n = 12,13,14,and 15 by showing how to
break classes of these sizes into groups of 4 or 5 students,
12 = 4 + 4 + 4
13 = 4 + 4 + 5
14 = 4 + 5 + 5
15 = 5 + 5 + 5
Inductive step,We must show that P(12),...,P(n) imply P(n + 1) for all n ≥ 15,
Thus,we assume that P(12),...,P(n) are all true and show how to divide up a
class of n + 1 students,We?rst form one group of 4 students,Then we can divide
the remaining n? 3 students into groups of 4 or 5 by the assumption P(n? 3),
(Note that n ≥ 15 and so n? 3 ≥ 12; thus,P(n? 3) is among our assumptions
P(12),...,P(n).) This proves P(n + 1),and so the claim holds by induction,
Problem 5,
Claim,If a collection of positive integers (not necessarily distinct) has sum n ≥ 1,then the
collection has product at most 3
n/3
,
For example,the collection 2,2,3,4,4,7 has the sum,
5 Problem Set 2
2 + 2 + 3 + 4 + 4 + 7 = 22
On the other hand,the product is,
2 2 3 4 4 7 = 1344 · · · · ·
≤ 3
22/3
3154.2≈
(a) As a preliminary step,use strong induction to prove that n ≤ 3
n/3
for every inte-
ger n ≥ 0.
Solution,The proof is by strong induction,Let P(n) be the proposition that n ≤
3
n/3
.
Base case,We show that P(0),P(1),P(2),P(3),and P(4) are true:
0
3
≤ 3
0
→ 0 ≤ 3
0/3
1
3
≤ 3
1
→ 1 ≤ 3
1/3
2
3
≤ 3
2
→ 2 ≤ 3
2/3
3
3
≤ 3
3
→ 3 ≤ 3
3/3
4
3
≤ 3
4
→ 4 ≤ 3
4/3
Each implication follows by taking cube roots,
Inductive step,Now,we show that P(0),...,P(n) imply P(n+ 1) for all n ≥ 4,Thus,
we assume that P(0),...,P(n) are all true and reason as follows,
3
(n+1)/3
= 3 3
(n?2)/3
·
3 · (n? 2)≥
n + 1 (for all n ≥ 7/2)≥
The?rst step is algebra,The second step uses our assumption P(n? 2),The third
step is a linear inequality that holds for all n ≥ 7/2,(This forced us to deal individ-
ually with the cases P(3) and P(4),above.) Therefore,P(n + 1) is true,and so P(n)
is true for all n ≥ 0 by induction,
(b) Prove the claim using induction or strong induction,(You may?nd it easier to
use induction on the number of positive integers in the collection rather than induction
on the sum n.)
Solution,We use induction on the size of the collection,Let P(k) be the proposition
that every collection of k positive integers with sum n has product at most 3
n/3
,
First,note that P(1) is true by the preceding problem part,
6 Problem Set 2
Next,we must show that P(k) implies P(k + 1) for all k ≥ 1,So assume that P(k)
is true,and let x
1
,...,x
k+1
be a collection of positive integers with sum n,Then we
can reason as follows,
x
1
x
2
···x
k
·x
k+1
≤ 3
(n?x
k+1
)/3
·x
k+1
·
≤ 3
(n?x
k+1
)/3
3
x
k+1
/3
·
= 3
n/3
The?rst step uses the assumption P(k),the second uses the preceding problem part,
and the last step is algebra,This shows that P(k + 1) is true,and so the claim holds
by induction,
Problem 6,Suppose that you take a piece of paper and draw n straight lines,no one
exactly on top of another,that completely cross the paper,This divides the paper into
polygonal regions,Prove by induction that you can color each region either red or blue
so that two regions that share a boundary are always colored differently,(Regions that
share only a boundary point may have the same color.)
Solution,The proof is by induction,Let P(n) be the proposition that the regions
de?ned by n lines can be colored red or blue so that adjacent regions are different colors,
Base case,If n = 0,then there are no lines and the whole paper is a single region,Color
it red,Adjacent regions are different colors trivially since there are no adjacent regions,
Thus,P(0) is true,
Inductive step,Assume that P(n) is true,We prove that P(n + 1) is also true,Given
a con?guration of n + 1 lines,remove an arbitrary line l,By the assumption P(n),the
polygonal regions de?ned by the remaining n lines can be colored red or blue so that
adjacent regions are colored differently,Now add back the line l and invert the color of
every region to one side of l,Adjacent regions on the same side of the line are different
colors by the induction assumption P(n),Adjacent region on opposite sides of the line
are different colors because the colors on one side were inverted,Therefore,P(n) implies
P(n + 1),and so P(n) is true for all n ≥ 0 by induction,
Problem 7,Let’s consider a variation of the Unstacking game demonstrated in lecture,As
before,the player is presented with a stack of n ≥ 1 bricks,Through a sequence of moves,
she must reduce this to n single-brick stacks while scoring as many points as possible,A
move consists of dividing a single stack of (a + b) bricks (where a,b > 0) into two stacks
with heights a and b,Suppose that this move is worth a+ b points,Find the best strategy
and use induction to prove that there is no better strategy,
Solution,Some experimentation suggests that the best strategy is to remove one block
Problem Set 2 7
at a time,This gives a score of,
n(n + 1)
n + (n? 1) +,.,+ 3 + 2 =? 1
2
(n + 2)(n? 1)
=
2
Now we must prove that there is no better strategy,
Proof,We use strong induction,Let P(n) be the proposition that unstacking n bricks is
worth at most (n + 2)(n? 1)/2 points,
Base case,P(1) is true because the game ends immediately when there is only 1 brick,
Thus,the player’s score is 0,which is the value of (n + 2)(n? 1)/2 when n = 1,
Inductive step,Now assume that P(1),...,P(n? 1) are all true in order to prove P(n),
where n ≥ 2,Suppose the stack of n bricks is split into stacks of height x and n? x,where
0 < x < n,The player’s best possible score for the game is then,
((n? x) + x)+ (x + 2)(x? 1)/2+(n? x + 2)(n? x? 1)/2
for?rst move to unstack x bricks to unstack n? x bricks
Here we are using the assumptions P(x) and P(n? x),which specify the best possible
scores for unstacking x and n? x bricks,Now we must choose x to maximize this expres-
sion,The derivative with respect to x is 2x? n,Thus,the expression decreases as x grows
from 1 to n/2 and then increases symmetrically as x grows
from n/2 to n? 1,Therefore,the maximum is achieved when x = 1 or x = n? 1,In
both cases,the expression above is equal to,
(n + 2)(n? 1)
2
So we have shown that P(1),.,,,P(n? 1) imply P(n),
Therefore,P(n) is true for all n ≥ 1 by the strong induction principle,
