COMP10020 – Discrete Maths – Induction (part 2)

A better Example

Let’s take a look at another example, this time lets use:

_n          

∑ i²   =     (n(n+1)(2n+1)) / 6

ⁱ⁼⁰           

 

Where we have:

 

                _n

L(n) =    ∑ i²                          and                        R(n) =    (n(n+1)(2n+1)) / 6

                ⁱ⁼⁰

 

For now I will skip the base case. However, do note that when n=0 for the base case, L(0)=R(0), so that the base case is true. As for the step cases, we have:

 

• ∑ i²  =  ∑ (n+1)²

 

Once this is done, we then need to move everything next to the ‘∑’ onto the right hand side. So we get this:

 

• before we move we have:
             R(n)     =          (n(n+1)(2n+1)) / 6
• Once the ‘i’ has be moved over, then R(n) becomes R(n+1), and we have:
             R(n+1) =          [(n(n+1)(2n+1)) / 6]   +  (n+1)²

 

Once we have this, it is just simple arithmetic:

 

(1) = [(n(n+1)(2n+1)) / 6]  +  (n+1)²

(2) = [(n(n+1)(2n+1)) / 6]  +  [6(n+1)² / 6]               make both have same denominator.

(3) = (n(n+1)(2n+1) + 6(n+1)²) / 6                             bring both together

(4) = ((n+1)(n+2)(2n+3)) / 6                                  

(5) = R(n+1)

 

As from before, step (4) requires you to expand the brackets from step (3), the fractionise the whole lot to obtain (n+1)(n+2)(2n+3).