A proof induction has two standard parts The first establish

A proof induction has two standard parts. The first establishing that a theorem is true for some small (usually almost always trivial. Next, an inductive hypothesis is the theorem is assumed to be true for all cases up to some the theorem is then shown to be true for the next value proves the theorem (as long as k is finite). As an example, we prove that the Fibonacci numbers, F_4 = 5, ..., F_i = F_i-1 + F_i-2, satisfy F_i

Solution

The induction proof works by verifying whether the example works for all possible values.. Let us see how it works..

For example :: Consider E(n) 1² + 2² + 3² + ... + n² = (1/6). n.(n+1).(2n+1)

Now, we need to prove that the above example is true for all possible values..

So, first we consider n = 1.. For n = 1, obviously the sequence is true..

For n=1, LHS = 1²

                RHS = (1/6).1.(1+1).(2+1) = 6/6 = 1

here LHS = RHS..

Now we have to prove that : if E(k) is true, then E(k+1) is true..

Let us consider E(K) is true..

We have to prove that property is valid for n = k+1
We have to prove: 1² + 2² + 3² + ... + k² + (k+1)² = (1/6).(k+1).(k+2)(2k+3)

Left side

= 1² + 2² + 3² + ... + k² + (k+1)²

= (1² + 2² + 3² + ... + k²) + (k+1)(k+1)

= (1/6). k.(k+1).(2k+1) + (k+1)(k+1)

= (1/6).(k+1). [ k(2k+1) + 6(k+1)]

= (1/6).(k+1).(2 k² + 7k + 6)

Right side

= (1/6).(k+1).(k+2)(2k+3)

= (1/6).(k+1).(2k² + 3k + 4k + 6)

Here, LHS = RHS.. I.e., this is true for E(k+1) therefore our assumption is true..

That means the equation is true for all possible values by principle of induction..