UMBC CMSC203 Discrete Structures, Section 06, Spring 2016

Homework 8, Due Thursday, 04/07

Instructions: In the following questions you are asked to use proof by induction. Your proof must not simply be a sequence of equations, even if the statement you are proving is arithmetic in nature. Clearly indicate using complete English sentences: 1) what you are allowed to assume from the induction hypothesis, 2) what you need to show to establish the induction step, and 3) which steps of the proof uses the induction hypothesis.

Responses that do not include well-written English sentences that clearly explain your proof will receive a grade of no more than 50%.

1. Induction (cubes). Prove by induction that for all integers n ≥ 1

   1³ + 2³ + 3³ + ⋅⋅⋅ n³ = [ n (n+1) / 2]²

2. Induction (fractions). Prove by induction that for all integers n ≥ 1

   1 1⋅5

   +

   1 5⋅9

   +

   1 9⋅13

   +  ⋅⋅⋅  +

   1 (4 n - 3) (4 n + 1)

   =

   n 4 n + 1

   .

3. Regular Graphs, Revisited. Recall that in graph theory, a k-regular graph is an undirected graph where every vertex has degree k. Here we do not allow edges from a vertex to itself (self loops) and we do not allow more than one edge between a pair of vertices. Also recall that the degree of a vertex is simply the number of edges incident on that vertex.

   Prove by induction on k that for every k ≥ 0, there exists a k-regular graph.

4. Induction (inequality). Let x ≥ 0 be a real number. Prove by induction on n, that for all n ≥ 2,

   1 + nx ≤ (1 + x)ⁿ.

   Hint: Do not expand (1 + x)ⁿ all the way. Use induction!

   Note: the inequality actually holds for x ≥ −1, but for this exercise you will only prove the easy case.