Sec. 8.2 Solutions by Jason Brudvik
9•• Prove by induction that the hypercube Hn has 2n points.
Basis: H0 has 1 point, and 1 = 20
Induction Step:
Each successive hypercube has twice as many points as the previous, by definition.
Therefore Hn+1 has 2*2n = 2n+1 points.
10••• How many edges are in a hypercube Hn? Prove your answer by induction.
Hn has n*2n-1 edges.
Proof by Induction:
Basis: H0 has 0 edges, and 0 = 0*2-1
Induction Step: Assume Hn has n*2n-1 edges. We want to show Hn+1 has (n+1)*2n edges.
By definition, Hn+1 is two copies of Hn plus lines connected between corresponding points.
Therefore the number of edges for Hn+1 is:
2*{the number of edges in Hn} + {the number of points in Hn}
= 2*n*2n-1 + 2n
= n*2n + 2n
= (n+1)*2n