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 condition 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$

adamponting.com

induction by the method of undetermined coefficients

Leave a Reply Cancel reply