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{align} 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{align}\] 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{align} 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{align}\] Substituting \(A_1=A_2=\frac{1}{2}\) into \((1)\) gives \[\begin{align} 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{align}\] 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{align} 1+2 & = { A }_{ 0 }+\frac { 1 }{ 2 } \times 2+\frac { 1 }{ 2 } \times { 2 }^{ 2 } \\ 3 & = { A }_{ 0 }+1+2 \\ { A }_{ 0 } & = 0. \end{align}\] 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{align} { 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{align} \] 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{align} { \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{align} \] 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{align} { 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{align} \] On substituting this into the original equation, \[\begin{align} { 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{align}\] 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{equation} \begin{split} 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{split} \end{equation} \] 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\]