induction by the method of undetermined coefficients

1. Assume the general form of the answer
2. Impose the condition that the induction be true for n=0 (or other convenient value)
3. Impose the induction consition that the step from m-1 to m be true.
4. From 2 and 3, determine the unknown coefficients.

Example. Find the formula for 1^3+2^3+3^3+4^3+\dots+n^3

Since \sum n = \frac{n(n+1)}{2} and \sum n^2 = \frac{n(n+1)(2n+1)}{6} , it seems the closed form of \sum n^p will be a polynomial of degree p+1. (Educated guess.)
Step 1. Write a polynomial of degree 4, with 5 undetermined coefficients:


Step 2. With n=0, i.e. no terms, we get e=0.
Step 3. Apply the induction step from m-1 to m : add m^3 to both sides, and substitute m-1 for n.


If the induction is to work, the RHS must be equal to am^4+bm^3+cm^2+dm.
Step 4. Equate the two expressions:


Rearrange the LHS. Use binomial expansion, and arrange coefficients to match the RHS powers of m:

    \begin{align*}  &&m^4&( & a)&&&&&& &\\ &+&m^3&(&-4a&&+b&&+1)&&&\\ &+&m^2&(&6a&&-3b&&+c)&&&\\ &+&m&(&-4a&&+3b&&-2c&&+d)&\\ &+&&(&a&&-b&&+c&&-d)&=am^4+bm^3+cm^2+dm \end{align*}

Equating the coefficients of m^3, we get \quad -4a+b+1=b \quad\to\quad a=\frac{1}{4}.
Equating the coefficients of m^2, we have \quad6a=3b \quad\to\quad b=\frac{1}{2}.
Equating the coefficients of m, we have \quad-4a+3b-2c=0 \quad\to\quad c=\frac{1}{4}.
And from a-b+c-d=0 \quad\to\quad d=0.
Now the coefficients are determined, and the sought formula is:


Leave a Reply

Your email address will not be published. Required fields are marked *