Extremely difficult proof by induction?

The mathematical details are shown in the accompanying image.

Please note that this is not "inductive" as specified, but is, rather, a proof with motivation.

Line 1: Expand (k-1)^i as a binomial and show the first term explicitly.

Line 2: Assume k is an integer and sum both sides for each positive integer up to n.

Line 3: Notice that the first term on the rhs is n^i greater than the lhs - subtract like terms.

Line 4: Rearrange for n^i in terms of the summations. Call this equation 1.

Line 5: Notice that same derivation would work for i->i+1 giving equation for n^(i+1). Call this equation 2.

Line 6: Show first term of summation in equation 2 explicitly. Notice it's binomial coefficient is just i+1.

Line 7: Rearrange for this term.

Line 8: Change dummy index in summation j->j+1 so that the limits are j=1..i.

Line 9: Use equation 1 to replace n^(i+1) = nn^i in line 8.

Line 10: Multiply first sum through by n and factor out the summation over j.

Line 11: Divide through by i+1. This line is the required formula.

The techniques used in this method may also give you some insight as to how to produce an inductive proof.

Wishing you the best of luck!