Method of Undetermined Coefficients

Method of undetermined coefficients is used for finding a general formula for a specific summation problem. The method can only be used if the summation can be expressed as a polynomial function.

The method involves comparing the summation to a general polynomial function followed by simplification.

Let's start with an easy and well-known summation.

Find a general formula for $1 + 2 + 3 + \dots + n.$

---

Let's start by assuming that the above summation can be expressed as a polynomial function $f\left( n \right)$ of the form $$f\left( n \right) = { A }_{ 0 }+{ A }_{ 1 }n+{ A }_{ 2 }{ n }^{ 2 }+{ A }_{ 3 }{ n }^{ 3 }+\cdots.$$ Let's equate this function to our original summation: $$1 + 2 + 3 + \dots + n = { A }_{ 0 }+{ A }_{ 1 }n+{ A }_{ 2 }{ n }^{ 2 }+{ A }_{ 3 }{ n }^{ 3 }+\cdots. \qquad (1)$$ Now we want to simplify this equation. There's no easy way to simplify this because the left-hand side is not a proper expression. We first need to express the left-hand side as a proper expression.

The easiest way to do this is to compare the above expression to the summation $1 + 2 + 3 + \dots + n + \left( n+1 \right)$.

We know that $$\begin{aligned} 1+2+3+\cdots +n+\left( n+1 \right) & = f\left( n+1 \right) \\ 1+2+3+\cdots +n+\left( n+1 \right) & = { A }_{ 0 }+{ A }_{ 1 }\left( n+1 \right) +{ A }_{ 2 }{ \left( n+1 \right) }^{ 2 }+{ A }_{ 3 }{ \left( n+1 \right) }^{ 3 }+\cdots. \qquad (2) \end{aligned}$$ Then taking $(2)-(1)$ gives $$n + 1 = { A }_{ 1 }+\left( 2n+1 \right) { A }_{ 2 }+\left( 3{ n }^{ 2 }+3n+1 \right) { A }_{ 3 }+\cdots.$$ Since this expression works for all positive integers $n$, we can compare the degrees of the left-hand side and right-hand side. But before we do that, it's worth noting that the highest degree on the left-hand side is 1. For this equation to satisfy all values of $n$, the degree of the right-hand side must also be 1. Hence we can eliminate all variables on the right except for ${ A }_{ 1 }+\left( 2n+1 \right) { A }_{ 2 }$ because all other values are 0. Then the new equation is $$n+1={ A }_{ 1 }+\left( 2n+1 \right) { A }_{ 2 },$$ which gives $$\begin{aligned} n+1 & = { A }_{ 1 }+\left( 2n+1 \right) { A }_{ 2 } \\ & = 2{ A }_{ 2 }n+\left( { A }_{ 1 }+{ A }_{ 2 } \right)\\ \\ 2A_2 & = 1, ~A_1+A_2=1\\ \Rightarrow A_1&=A_2=\frac{1}{2}. \end{aligned}$$ Substituting $A_1=A_2=\frac{1}{2}$ into $(1)$ gives $$\begin{aligned} 1+2+3+\dots +n & = { A }_{ 0 }+{ A }_{ 1 }n+{ A }_{ 2 }{ n }^{ 2 }+{ A }_{ 3 }{ n }^{ 3 }+\cdots \\ & = { A }_{ 0 }+\frac { 1 }{ 2 } n+\frac { 1 }{ 2 } { n }^{ 2 }+0\cdot { n }^{ 3 }+\cdots \\ &={ A }_{ 0 }+\frac { 1 }{ 2 } n+\frac { 1 }{ 2 } { n }^{ 2 }. \end{aligned}$$ Now we just need to find the value of ${ A }_{ 0 }$, which is easy. Since the above expression is true for all values of $n$, we can just try substituting a specific value of $n$ into the equation and then find the value of ${ A }_{ 0 }$. For simplicity, let's try $n = 2$ (but you can also try any other positive integer $n$): $$\begin{aligned} 1+2 & = { A }_{ 0 }+\frac { 1 }{ 2 } \times 2+\frac { 1 }{ 2 } \times { 2 }^{ 2 } \\ 3 & = { A }_{ 0 }+1+2 \\ { A }_{ 0 } & = 0. \end{aligned}$$ Therefore, we have now completely simplified the equation. Expressing it in proper form, we have \[\begin{align} 1+2+3+\cdots +n & = \frac { 1 }{ 2 } n+\frac { 1 }{ 2 } { n }^{ 2 } \\
& = \frac { { n }^{ 2 }+n }{ 2 } \\ & = \frac { n\left( n+1 \right) }{ 2 }. \ _\square \end{align}\]

Let's try a slightly harder version of this problem. Before seeing the solution, try figuring out the answer on your own!

Find a general formula for ${ 1 }^{ 2 }+{ 2 }^{ 2 }+{ 3 }^{ 2 }+\cdots +{ n }^{ 2 }.$

---

As in the previous problem, we have $$\begin{aligned} { 1 }^{ 2 }+{ 2 }^{ 2 }+\cdots +{ n }^{ 2 }&={ A }_{ 0 }+{ A }_{ 1 }n+{ A }_{ 2 }{ n }^{ 2 }+{ A }_{ 3 }{ n }^{ 3 }+{ A }_{ 4 }{ n }^{ 4 }+\cdots \\ { 1 }^{ 2 }+{ 2 }^{ 2 }+\dots +{ n }^{ 2 }+{ \left( n+1 \right) }^{ 2 }&={ A }_{ 0 }+{ A }_{ 1 }\left( n+1 \right) +{ A }_{ 2 }{ \left( n+1 \right) }^{ 2 }+{ A }_{ 3 }{ \left( n+1 \right) }^{ 3 }+{ A }_{ 4 }{ \left( n+1 \right) }^{ 4 }+\cdots. \end{aligned}$$ On subtracting the equations, $${ \left( n+1 \right) }^{ 2 }={ A }_{ 1 }+{ A }_{ 2 }\left( 2n+1 \right) +{ A }_{ 3 }\left( 3{ n }^{ 2 }+3n+1 \right) +{ A }_{ 4 }\left( 4{ n }^{ 3 }+6{ n }^{ 2 }+4n+1 \right) +\cdots.$$ The variables on right-hand side with a degree greater than 2 can be discarded: $$\begin{aligned} { \left( n+1 \right) }^{ 2 }&={ A }_{ 1 }+{ A }_{ 2 }\left( 2n+1 \right) +{ A }_{ 3 }\left( 3{ n }^{ 2 }+3n+1 \right) \\ { n }^{ 2 }+2n+1&={ A }_{ 1 }+{ A }_{ 2 }\left( 2n+1 \right) +{ A }_{ 3 }\left( 3{ n }^{ 2 }+3n+1 \right). \end{aligned}$$ On expressing in proper form, $${ n }^{ 2 }+2n+1=3{ A }_{ 3 }{ n }^{ 2 }+\left( 2{ A }_{ 2 }+3{ A }_{ 3 } \right) n+\left( { A }_{ 1 }+{ A }_{ 2 }+{ A }_{ 3 } \right) .$$ On comparing the degrees, $$\begin{aligned} { n }^{ 2 }=3{ A }_{ 3 }{ n }^{ 2 }&\Rightarrow { A }_{ 3 }=\frac { 1 }{ 3 } \\ 2n=\left( 2{ A }_{ 2 }+3{ A }_{ 3 } \right) n\Rightarrow 2=2{ A }_{ 2 }+3{ A }_{ 3 }&\Rightarrow A_2=\frac { 1 }{ 2 } \\ 1={ A }_{ 1 }+{ A }_{ 2 }+{ A }_{ 3 }&\Rightarrow { A }_{ 1 }=\frac { 1 }{ 6 }. \end{aligned}$$ On substituting this into the original equation, $$\begin{aligned} { 1 }^{ 2 }+{ 2 }^{ 2 }+\cdots +{ n }^{ 2 } &={ A }_{ 0 }+{ A }_{ 1 }n+{ A }_{ 2 }{ n }^{ 2 }+{ A }_{ 3 }{ n }^{ 3 }+{ A }_{ 4 }{ n }^{ 4 }+\cdots \\ &={ A }_{ 0 }+\frac { 1 }{ 6 } n+\frac { 1 }{ 2 } { n }^{ 2 }+\frac { 1 }{ 3 } { n }^{ 3 }+{ A }_{ 4 }{ n }^{ 4 }+\cdots \\ &={ A }_{ 0 }+\frac { 1 }{ 6 } n+\frac { 1 }{ 2 } { n }^{ 2 }+\frac { 1 }{ 3 } { n }^{ 3 }, \end{aligned}$$ since variables with degree greater than 3 can be removed.

Now, since all values of $n$ work, we can substitute a value of $n$ to find the value of ${ A }_{ 0 }$. For $n = 1$, $${ 1 }^{ 2 }={ A }_{ 0 }+\frac { 1 }{ 6 } \times 1+\frac { 1 }{ 2 } \times { 1 }^{ 2 }+\frac { 1 }{ 3 } \times { 1 }^{ 3 }={ A }_{ 0 }+\frac { 1 }{ 6 } +\frac { 1 }{ 2 } +\frac { 1 }{ 3 } \Rightarrow { A }_{ 0 }=0.$$ Hence, \[\begin{align} { 1 }^{ 2 }+{ 2 }^{ 2 }+{ 3 }^{ 2 }+\cdots +{ n }^{ 2 } & = \frac { 1 }{ 6 } n+\frac { 1 }{ 2 } { n }^{ 2 }+\frac { 1 }{ 3 } { n }^{ 3 } \\
& = \frac { 2{ n }^{ 3 }+3{ n }^{ 2 }+n }{ 6 } \\
& = \frac { n\left( n+1 \right) \left( 2n+1 \right) }{ 6 }.\ _\square \end{align}\]

Can you now find a general formula for the sum of cubes or fourth powers?

Find a general formual for $1\cdot2+2\cdot3+3\cdot4+\cdots+n(n+1).$

---

We have $$\begin{aligned} 1\cdot2+2\cdot3+\cdots+n(n+1)=& A_{0}+A_{1}n+A_{2}n^2+\cdots \\ 1\cdot2+2\cdot3+\cdots+n(n+1)+(n+1)(n+2)=& A_{0}+A_{1}(n+1)+A_{2} (n+1)^2+\cdots. \end{aligned}$$ By subtracting, we have $$(n+1)(n+2)=A_{1}+A_{2}(2n+1)+A_{3}\left(3n^2+3n+1\right)+A_{4}\left(4n^3+6n^2+4n+1\right)+\cdots.$$ By comparing corresponding coefficients, we get $$3A_{3}=1,\quad 3A_{3}+2A_{2}=3,\quad A_{1}+A_{2}+A_{3}=2,$$ which gives $$A_{3}=\dfrac{1}{3},\quad A_{2}=1, \quad A_{1}=\dfrac{2}{3}.$$

Our sum then becomes $$1\cdot2+2\cdot3+\cdots+n(n+1) = A_0 + \dfrac{2}{3}n+n^2+\dfrac{1}{3}n^3.$$ To find $A_{0}$, substitute $n=1$, then the series reduces to its first term: $$2=A_{0}+2 \Rightarrow A_{0}=0.$$ On simplifying and factorizing, $$1\cdot2+2\cdot3+3\cdot4+\cdots+n(n+1)=\dfrac{1}{3}n(n+1)(n+2).\ _\square$$