The basis of induction

Proof by induction is a very powerful technique, used at all levels in maths, and really simple in principle.

You want to prove a proposition which depends on n. Let's call it P_n

First you prove it for a specific n, say 1.

So P₁ is true.

Then you prove that P_n ⇒ P_n+1

In other words, if P_n is true then P_n+1 must be true.

Then you have proved it for all n≥1.

If the proposition is a formula for a sum:

P_n: ∑ⁿ s_r = f(n)
then the easiest way to prove the induction step is probably to prove that

f(n+1)-f(n)=s_n+1

Whatever form f has, subtracting the two will probably be easier to do algebraically, probably a lot of ugly things will cancel out.