Chapter 5 Induction152
(j) 9 n: 9 m > n:ŒP.2n/AND NOT.P.2m//ç(k)Œ 9 n:P.n/çIMPLIES 8 n: 9 m > n:P.m/(l) NOT.P.0//IMPLIES 8 n:NOT.P.2n//Problem 5.15.
Consider the following sequence of predicates:
Q 1 .x 1 / WWD x 1
Q 2 .x 1 ;x 2 / WWD x 1 IMPLIESx 2
Q 3 .x 1 ;x 2 ;x 3 / WWD .x 1 IMPLIESx 2 /IMPLIESx 3
Q 4 .x 1 ;x 2 ;x 3 ;x 4 / WWD ..x 1 IMPLIESx 2 /IMPLIESx 3 /IMPLIESx 4
Q 5 .x 1 ;x 2 ;x 3 ;x 4 ;x 5 / WWD ...x 1 IMPLIESx 2 /IMPLIESx 3 /IMPLIESx 4 /IMPLIESx 5
::
:::
:
LetTnbe the number of different true/false settings of the variablesx 1 ;x 2 ;:::;xn
for whichQn.x 1 ;x 2 ;:::;xn/is true. For example,T 2 D 3 sinceQ 2 .x 1 ;x 2 /is
true for 3 different settings of the variablesx 1 andx 2 :
x 1 x 2 Q 2 .x 1 ;x 2 /
T T T
T F F
F T T
F F T(a)ExpressTnC 1 in terms ofTn, assumingn 1.(b)Use induction to prove thatTn D^13 .2nC^1 C. 1/n/forn 1. You may
assume your answer to the previous part without proof.
Problem 5.16.
You are givennenvelopes, numbered0;1;:::;n 1. Envelope 0 contains 20 D 1
dollar, Envelope 1 contains 21 D 2 dollars,... , and Envelopen 1 contains 2 n ^1
dollars. LetP.n/be the assertion that:
For all nonnegative integersk < 2n, there is a subset of thenenvelopes
whose contents total to exactlykdollars.Prove by induction thatP.n/holds for all integersn 1.