induction proof help

Loom

New member
Joined
Jul 24, 2013
Messages
2
QQ图片20130920165809.jpgQQ图片20130920165828.jpg
I stuck on the induction step. my TA suggest me use cases for even quantity and odd quantity of P(n)
 
In my opinion induction is a terrible way to prove it, but since you are required to use it:

Assume it is true for n. If n is even then there are n/2 even integers in [n]={1,...,n} ([n] is shorthand I use for this). The set [n+1] contains the same number of even integers. Since by assumption there are 2^(n/2) possible subsets of even integers in [n], there are also 2^(n/2) subsets in [n+1]. And n/2=floor((n+1)/2).

Now assume n is odd. This is the "hard" case. Now [n+1] has one more even integer than [n]. For each subset A of even integers in [n], there are now two sets of even integers in [n+1], namely A and A U {n+1}. Can you formalize it from here?

A much shorter proof looks like this: Len E(n) be the set of even integers in [n]. Since there are floor(n/2) even integers in [n], |E(n)|=floor(n/2). Thus the number of subsets of these even integers is 2^|E(n)| = 2^(floor(n/2)).
 
Top