Question

1. Use induction to prove that Summation with n terms where i=1 and Summation 3i 2 − 3i + 1 = n^3 for all n ≥ 1.

2. Let X be the set of all natural numbers x with the property that x = 4a + 13b for some natural numbers a and b. For example, 30 ∈ X since 30 = 4(1) + 13(2), but 5 ∈/ X since there’s no way to add 4’s and 13’s together to reach 5. (It’s not a multiple of 4, and adding 13 goes over.) Use strong induction to prove that n ∈ X for all integers n ≥ 36. Hint: it should be easy to show that k + 1 ∈ X if k − 3 ∈ X. You may need multiple base cases for this problem

Answer 1

1. We will use induction on n to prove that ,

Base step : For n =1 .

So the statement is true for n=1 .

Induction Hypothesis : Suppose the statement is true for n= m that is ,

Induction Step : For n =m+1 .

, using induction hypothesis .

So the statement is true for n=m+1 if we assume that it is true for n=m . Also the statement is true for n=1. Hence by induction on n the statement is true for all natural number n .

Hence for all .