Prove the formula below using mathematical induction

Question

n

∑ log2^k = ((n²+n)÷2) log2

k=1

Answer 1

By showing that a statement is true for an initial value of n, and that the truth at any value can be used to demonstrate the truth at the next value of n, mathematical induction proves that a statement is true for any value equal to or greater than the initial value.

The two steps to proof by mathematical induction are:

1 - Proving the base case

2 - Proving the induction step

1 - Base Case

We need to show that this holds for the first value of n. Since the left side of this equation is a summation beginning at k = 1, n = 1 is the lowest value we can consider - this is our base case.

n

∑ log2^k = ((n²+n)/2) log2

k=1

1

∑ log2^k = ((1²+1)/2) log2

k=1

log2 = log2

The base case holds! Now we need to show that the induction step holds.

2 - Induction step.

We need to show that if this equation holds for n = a, that it will also hold for n = a + 1

Assume:

a

∑ log2^k = ((a²+a)/2) log2

k=1

Need to prove:

a + 1

∑ log2^k = (((a+1)²+(a+1))/2) log2

k=1

Lets start with the left side of what we need to prove. First step we will separate the final term in the summation from the rest (what we already had in the assumption)

a+1 a a+1 a

∑ log2^k = ∑ log2^k + ∑ log2^k = ∑ log2^k + log2^{a + 1}

k=1 k=1 k=a+1 k=1

Using our induction step assumption, we can substitute for the summation on the right side of the above

a+1 a

∑ log2^k = ∑ log2^k + log2^{a + 1} = ((a²+a)/2) log2 + log2^{a + 1}

k=1 k=1

Finally, we brush the rust off the algebra skills to rewrite the right side further

((a²+a)/2) log2 + log2^{a + 1} =

((a²+a)/2) log2 + (a + 1)log2 =

((a²+a)/2) log2 + ((2a + 2)/2)log2 =

((a²+3a + 2)/2) log2 =

(((a + 1)² + (a + 1))/2) log2

Therefore,

a+1

∑ log2^k = (((a + 1)² + (a + 1))/2) log2

^a

Therefore the induction step holds.

---------------

Having proven both the base case and the induction step, mathematical induction proves that:

n

∑ log2^k = ((n²+n)÷2) log2

k=1