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:

    \[1^3+2^3+3^3+4^3+\dots+n^3=an^4+bn^3+cn^2+dn+e\]

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.

    \[1^3+2^3+3^3+\dots+(m-1)^3+m^3=a(m-1)^4+b(m-1)^3+c(m-1)^2+d(m-1)+m^3\]

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:

    \[a(m-1)^4+b(m-1)^3+c(m-1)^2+d(m-1)+m^3=am^4+bm^3+cm^2+dm\]

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:

    \[\frac{n^4}{4}+\frac{n^3}{2}+\frac{n^2}{4}=\frac{n^2(n^2+2n+1)}{4}=\left(\frac{n(n+1)}{2}\right)^2\]

Leave a Reply

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