Strong Induction - Integrals

[XJellieBX]

Homework Statement

Prove, for r $$\geq$$ 1,

S_r(n) = $$\sum$$ k^r = (n^r+1)/(r+1) + P_r(n)

where Pr(n) is some polynomial with respect to n of degree r.
(Hint: Prove using strong induction on r. After you show the base case is true, assume the statement istrue for all r = 1,2, ... ,R-1 and then show the statement is true for r = R.)

Homework Equations

(r + 1) $$\sum$$ k^r = n^(r+1) + P_r(n) - $$\sum$$ [c₂k^r-1 + c₃k^r-2 + ... + c_rk + 1], where c_# is some constant.

The Attempt at a Solution

I tried to prove the base case (r=1), but I can't seem to complete it.
Using the equation given,
S_r(n) = $$\sum$$ k_r = (n^r+1)/(r+1)
-> the left side goes to: n²
And plugging in r=1, the right side goes to n²/2 + P_r(n)

Am I missing something? The two sides aren't equal at all, and I'm at a lost.

 

[mighty2000]

Please help!

Thank you for your post. I understand your confusion and will try my best to guide you through the proof.

First, let's start by defining Sr(n) as the sum of the first r powers of n, starting from 1. In other words, Sr(n) = 1 + 2 + ... + r. This is equivalent to \sum kr as given in the problem.

Now, let's look at the base case, r = 1. In this case, we have Sr(n) = \sum kr = 1. The right side of the equation becomes (n1+1)/(1+1) + Pr(n), where Pr(n) is some polynomial of degree 1. Simplifying this, we get (n+1)/2 + Pr(n).

Since our goal is to prove that the two sides are equal, we must show that (n+1)/2 + Pr(n) = 1. This is true if Pr(n) = 1 - (n+1)/2. Therefore, our base case is satisfied if we choose Pr(n) = 1 - (n+1)/2.

Now, let's assume that the statement is true for all r = 1,2,...,R-1. This means that we can write:

S(R-1)(n) = (n(R-1)+1)/(R-1+1) + P(R-1)(n)

Now, let's look at the case where r = R. We have:

SR(n) = \sum kR = (nR+1)/(R+1) + PR(n)

Using the given hint, we can write the right side as:

(n(R-1)+1)/(R-1+1) + PR(n) + c2(n(R-1)+1)^2 + c3(n(R-1)+1)^3 + ... + cR(n(R-1)+1)^R

This is because we assumed the statement is true for all r = 1,2,...,R-1. Now, we can simplify this to:

(n(R+1)+1)/(R+1) + PR(n) + c2(nR^2+2nR+1) + c3(nR^3+3nR^2+3nR+1) + ... + cR(nR^R+RnR