Arithmetic-Geometric Progression
An arithmetic-geometric progression (AGP) is a progression in which each term can be represented as the product of the terms of an arithmetic progressions (AP) and a geometric progressions (GP).
In the following series, the numerators are in AP and the denominators are in GP:
\[\large \dfrac{\color{blue}{1}}{\color{red}{2}}+\dfrac{\color{blue}{2}}{\color{red}{4}}+\dfrac{\color{blue}{3}}{\color{red}{8}}+\dfrac{\color{blue}{4}}{\color{red}{16}}+\dfrac{\color{blue}{5}}{\color{red}{32}}+\cdots= \, ?\]
Arithmetic-geometric progressions are nice to work with because their sums can be evaluated easily, and this tool is used in a variety of contest problems.
Definition
Let's start with a few simple definitions of the concepts that we will repeatedly use.
Arithmetic-Geometric Progression (AGP): This is a sequence in which each term consists of the product of an arithmetic progression and a geometric progression. In variables, it looks like
\[ a , (a+d) r , (a+2d) r^2 , (a+3d)r^3, \ldots , \left[ a + (n-1) d \right] r^{n-1},\]
where \(a\) is the initial term, \(d\) is the common difference, and \(r\) is the common ratio.
General term of AGP: The \(n^{\text{th}}\) term of the AGP is obtained by multiplying the corresponding terms of the arithmetic progression (AP) and the geometric progression (GP). So, in the above sequence the \(n^{\text{th}}\) term is given by
\[t_n=\left[ a + (n-1) d \right] r ^ { n -1}.\]
Sum of terms of AGP: The sum of the first \(n\) terms of the AGP is \( S_n=\displaystyle \sum_{k= 1 } ^ {n} \left[ a + (k-1) d \right] r ^ { k-1 }\), which can be solved further to obtain
\[S_n=\dfrac{a -\left[ a+(n - 1)d\right] r^{n}}{1 - r}+\dfrac{dr(1 - r^{n-1 })}{(1 - r)^2}.\]
Sum to infinity of AGP: If \( |r| < 1 \), then the sum to infinity is given by
\[ S_\infty = \dfrac{ a } { 1 - r } + \dfrac{ dr } { (1-r)^2 }. \]
Sum of AGP
If we wanted to find the sum of an AGP, we could manually calculate the total. However, this could be a tedious process, and the terms will quickly get too large or too small for us to easily sum them. Let's find a more general approach, and we start by looking at an example.
Find the sum of the series \(1 \cdot 2 +2 \cdot 2^2 +3 \cdot 2^3+\cdots+100 \cdot 2^{100}\).
The terms of this sequence are too large for us to want to attempt to sum them manually.
Let the sum of the series be \(S\), then
\[S= 1 \cdot 2+2 \cdot 2^2+3 \cdot 2^3+\cdots+100 \cdot 2^{100}.\]
On multiplying \(S\) by 2, we get
\[2S= 1\cdot 2^2+2 \cdot 2^3+\cdots+99 \cdot 2^{100}+100 \cdot 2^{101}.\]
Now subtracting \(2S\) from \(S\), we get
\[ \begin{array} { rlllllllll} S&= 1 \cdot 2&+2 \cdot 2^2&+3 \cdot 2^3&+\cdots+100 \cdot 2^{100} \\ 2S&= 0 &+1\cdot 2^2&+2 \cdot 2^3&+\cdots+99 \cdot 2^{100}&+&100 \cdot 2^{101}\\ \hline S(1-2)& = 1 \cdot 2&+1 \cdot 2^2&+1 \cdot 2^3&+\cdots+1 \cdot 2^{100}&-&100 \cdot 2^{101}.\\ \end{array}\]
Then we have
\[\begin{align} -S&=2\dfrac{(2^{100}-1)}{2-1}-100 \cdot 2^{101} \qquad (\text{since the first 100 terms are in GP})\\ S&=100 \cdot 2^{101}-2 \cdot 2^{100}+2\\ S&=200 \cdot 2^{100} - 2\cdot 2^{100}+2\\ S&=198 \cdot 2^{100}+2. \ _\square \end{align}\]
In this problem, the crucial step was to multiply by the common ratio and subtract the sequences, which allowed us to reduce it to a GP which we are familiar with. Now let's derive a general formula for the sum of terms of an AGP with initial term \(a\), common difference \(d\) and common ratio \(r\):
The sum of the first \(n\) terms of an AGP is given by
\[\begin{align} S_n &= \displaystyle \sum_{k = 1}^n \left[a + (k - 1) d\right] r^{k-1} \\\\ &= \dfrac{a -\left [a+(n - 1)d\right] r^{n}}{1 - r}+\dfrac{dr(1 - r^{n-1 })}{(1 - r)^2}. \end{align}\]
We'll use the same method of subtraction to find the sum of AGP that we used in the above example to prove this theorem:
To get the sum of the first \(n\) terms of an AGP, we need to find the value of
\[S= a+(a+d)r+(a+2d)r^2+\cdots+[a+(n-1)d]r^{n-1}.\]
Now let's multiply \(S\) by \(r\), then we get
\[Sr= 0 +ar+(a+d)r^2+\cdots+[a+(n-2)d]r^{n-1}+[a+(n-1)d]r^{n}.\]
Subtracting \(Sr\) from \(S\), we get
\[\begin{array} { rlllllllll} S&= a+(a+d)r&+(a+2d)r^2&+\cdots+[a+(n-1)d]r^{n-1}\\ Sr&= 0 +ar&+(a+d)r^2&+\cdots+[a+(n-2)d]r^{n-1}&+[a+(n-1)d]r^{n}\\ \hline S(1-r)& = a+dr&+dr^2&+\cdots+dr^{n-1}&-[a+(n-1)d]r^{n}.\\ \end{array}\]
If we were to exclude the first term and the last term, then the rest is a sum of geometric progression with first term \(dr\) and common ratio \(r\). Thus
\[\begin{align} S(1-r)&=a-[a+(n-1)d]r^{n}+\dfrac{dr(1-r^{n-1})}{1-r} \\ S&=\dfrac{a-[a+(n-1)d]r^{n}}{1-r}+\dfrac{dr(1-r^{n-1})}{(1-r)^2}. \ _\square \end{align}\]
Let's try one problem to practice the above method:
\[1+2 \cdot 2+ 3 \cdot 2^2 + 4 \cdot 2^3 + \cdots+ 100 \cdot 2^{99}= \, ?\]
Sum of AGP up to Infinite Terms
Now that we've found the sum of finitely many terms, let's consider the case of infinitely many terms. We certainly cannot manually sum up infinite terms, so we will have to find a general approach. We start by discussing the problem you encountered at the top of this page:
\[\large \dfrac{\color{blue}{1}}{\color{red}{2}}+\dfrac{\color{blue}{2}}{\color{red}{4}}+\dfrac{\color{blue}{3}}{\color{red}{8}}+\dfrac{\color{blue}{4}}{\color{red}{16}}+\dfrac{\color{blue}{5}}{\color{red}{32}}+\cdots=\, ?\]
Let us assume the given series to be \(S\), then
\[S=\dfrac 12 +\dfrac 24 +\dfrac 38+\dfrac{4}{16}+\dfrac{5}{32}+\cdots.\]
On multiplying \(S\) by \(\frac 12\), we get
\[ \dfrac S2=\dfrac 14 +\dfrac 28 +\dfrac{3}{16}+\dfrac{4}{32}+\dfrac{5}{64}+\cdots.\]
Now subtracting \(\frac S2\) from \(S\), we get
\[ \begin{array} { rlllllllll} S&=\dfrac 12 &+\dfrac 24 &+\dfrac 38 &+\dfrac{4}{16} &+\dfrac{5}{32}+ \cdots \\ \dfrac S2&=0&+\dfrac 14 & +\dfrac 28 & +\dfrac{3}{16}&+\dfrac{4}{32}+\dfrac{5}{64}+\cdots \\ \hline S \left(1- \dfrac 12 \right)& =\dfrac 12& +\dfrac 14 & + \dfrac 18 & +\dfrac{1}{16} & +\dfrac{1}{32} +\cdots \\ \Rightarrow \dfrac S2&=\dfrac 12 &+\dfrac 14 &+ \dfrac 18 &+\dfrac {1}{16} &+\dfrac {1}{32} +\cdots, \end{array}\]
which is a GP. Therefore, using the formula for the sum of infinite terms of GP, we get
\[S=2 \times \left( \dfrac{\dfrac{1}{2}}{1-\dfrac{1}{2}} \right)=2. \ _\square \]
We are now ready to state the sum of an infinite AGP, and will present the proof below:
The sum of infinite terms of an AGP is given by \(S_{\infty}=\dfrac{a}{1-r}+\dfrac{dr}{(1-r)^2}\) , where \(|r|<1\).
It is clear that if \( |r | \geq 1 \), then the term \( [a+(n-1)d]r^{n-1}\) gets arbitrarily large, and hence the sum does not converge. So we just have to consider the case of \( |r| < 1 \). We will be using the fact that in this case,
\[ \lim_{n\rightarrow \infty} r^n = 0 . \]
As we have discussed earlier, the sum of the first \(n\) terms in an AGP is given by
\[S_n = \sum_{k = 1}^n \left[a + (k - 1) d\right] r^{k - 1} = \dfrac{a -\left [a+(n - 1)d\right] r^n}{1 - r}+\dfrac{dr(1 - r^{n - 1})}{(1 - r)^2}. \]
Taking the limit as \(n\) goes to infinity, we get
\[\begin{align} \lim_{n \to \infty}S_{n} &= \dfrac{a-0}{1-r}+\dfrac{dr(1-0)}{(1-r)^2}\\ &=\dfrac{a}{1-r}+\dfrac{dr}{(1-r)^2}, \text{ where } |r|<1. \ _\square \end{align}\]
With this formula, we can quickly find the sum of infinitely many terms of a suitable AGP. Let's practice with more examples:
Calculate the value of the sum \(\displaystyle\sum_{i=1}^{\infty} \dfrac{i}{7^i}\).
The sum can be expanded as
\[S=\dfrac{1}{7}+\dfrac{2}{7^2}+\dfrac{3}{7^3}+\dfrac{4}{7^4}+\cdots .\]
To get the above series into the AGP form, we have to factor out the term \(\dfrac 17\) and then the series can be written as
\[S=\left( \dfrac 17 \right) \left( 1+\dfrac{2}{7}+\dfrac{3}{7^2}+\dfrac{4}{7^3}+\cdots \right) .\]
Clearly, this is an infinite AGP with \(a=1, r=\frac{1}{7}, d=1\).
Using the above formula, the sum \(S\) is \[\begin{align} \left( \dfrac 17 \right) \left( \dfrac{a}{1-r}+\dfrac{dr}{(1-r)^2} \right) &=\left( \dfrac 17 \right) \left( \dfrac{1}{1-\dfrac{1}{7}}+\dfrac{ 1 \times\frac{1}{7}}{\left(1-\dfrac{1}{7}\right)^2} \right) \\ &=\dfrac 17 \left( \dfrac 76+\dfrac{7}{36} \right)\\ &=\dfrac{7}{36}. \ _\square \end{align} \]
Calculate the value of the summation \(\displaystyle\sum_{i=1}^{\infty} \dfrac{2i-1}{2^{i+1}}\).
Solution 1:
Writing down the given summation as the difference of two summations, we get
\[\sum_{i=1}^{\infty} \dfrac{2i-1}{2^{i+1}}=\displaystyle\sum_{i=1}^{\infty} \left(\dfrac{2i}{2^{i+1}}-\dfrac{1}{2^{i+1}}\right)=\displaystyle\sum_{i=1}^{\infty}\dfrac{i}{2^i}-\displaystyle\sum_{i=1}^{\infty}\dfrac{1}{2^{i+1}}.\]
The first summation is an AGP with \( a =\frac{1}{2} \), \( d = 1 \), and \( r = \frac{1}{2} \). So the sum to infinity is \( \frac{ \frac{1}{2} } { 1 - \frac{1}{2} } + \frac{ 1 \times \frac{1}{2} } { ( 1- \frac{1}{2} ) ^ 2 } = 2 \).
The second summation is a geometric progression with the sum to infinity of \( \frac { \frac{1}{4} } { 1 - \frac{1}{2} } = \frac{1}{2} \).
Hence, the total is \( 2 - \frac{1}{2} = 1.5 \ _\square \).Solution 2:
The given series can be written as
\[\dfrac 14+\dfrac 38 +\dfrac{5}{16}+\dfrac{7}{32}+\cdots .\]
Multiplying and dividing the series by \(4\), we get
\[ \dfrac{1}{4} \left( 1+\dfrac{3}{2}+ \dfrac{5}{4}+\dfrac{7}{8}+ \cdots \right) .\]
Now clearly, the series is an AGP with \(a=1,d=2,r=\frac 12\).
Hence, using the formula for the sum of infinite terms of AGP, we get
\[S=\dfrac 14 \left( \dfrac{1}{1-\dfrac 12}+\dfrac{2 \cdot \dfrac 12}{ \left( 1-\dfrac 12 \right)^2} \right) =\dfrac 14 \left( 2+4 \right)=1.5. \ _\square \]
Solving the problems below will check if you have a grip over the concepts and problem solving:
Find the value of \(p\) given
\[ 3+\dfrac{1}{4}(3+p)+\dfrac{1}{4^{2}}(3+2p)+\dfrac{1}{4^3}(3+3p)+\cdots =8.\]
The value of \(\displaystyle \sum_{n=1}^ \infty \frac{ 2n}{ 3^n } \) can be expressed in the form \( \frac{a}{b} \), where \(a\) and \(b\) are coprime positive integers. Find \( a - b \).
Applications
In this section we will work out some examples and problems based on applications of AGP:
1. Recognizing an AGP
\(\text{}\)
Prove the following identity:\[\left( x^{n-1}+\frac{1}{x^{n-1}} \right) + 2 \left( x^{n-2} +\frac{1}{x^{n-2}} \right) +\cdots+(n-1) \left( x +\frac 1x \right) +n=\frac{1}{x^{n-1}} \left( \dfrac{x^n-1}{x-1} \right)^2.\]
We will start proving by rewriting the LHS of the identity as
\[\begin{align} &\left( x^{n-1}+\frac{1}{x^{n-1}} \right) + 2 \left( x^{n-2} +\frac{1}{x^{n-2}} \right) +\cdots+(n-1) \left( x +\frac 1x \right) +n\\ &=\left( \frac{1}{x^{n-1}}+\frac{2}{x^{n-2}}+\cdots+\frac{n-1}{x} \right) + \left[ x^{n-1}+2x^{n-2}+\cdots+(n-1)x \right] +n. \end{align}\]
Multiplying and dividing the expression in the parenthesis by \(x^{n}\), we get
\[\dfrac{1}{x^{n}} \left( x+2x^2+\cdots+(n-1)x^{n-1} \right) +\left[ x^{n-1}+2x^{n-2}+\cdots+(n-1)x \right] +n.\]
Using the formula for the sum of terms of an AGP for the expression in the parenthesis, we get
\[\dfrac{x \left( (n-1)x^n-nx^{n-1}+1\right)}{x^n(1-x)^2}+\left[ x^{n-1}+2x^{n-2}+\cdots+(n-1)x \right] +n.\]
Now, since the expression in the bracket can be obtained from the first term in the above expression by replacing \(x\) with \(\frac 1x\), we have
\[\dfrac{x [ (n-1)x^n-nx^{n-1}+1]}{x^n(1-x)^2} +\dfrac{\left( \frac 1x \right) \left[ (n-1)\left( \frac 1x \right)^n-n\left( \frac 1x \right)^{n-1}+1 \right]}{\left( \frac 1x \right)^n \left[ 1-\left( \frac 1x \right) \right]^2} +n.\]
Simplifying this further gives
\[\dfrac{1}{x^{n-1}} \left( \dfrac{x^n-1}{x-1} \right)^2=\text{RHS}.\]
Hence proved. \(_\square\)
What is the expected number of coin flips before we get the first head?
Let \(P(n)\) be the probability of gettinng first head in \(n\) flips, then \(P(n)=\left(\dfrac{1}{2}\right)^n\).
Hence, the expected number of coin flips is \(\displaystyle\sum_{n=1}^{\infty} nP(n)=\displaystyle\sum_{n=1}^{\infty} \dfrac{n}{2^n}=2. \ _\square\)
Let's see if you can solve the following problem.
If we roll one die, what is the expected number of dice throws before we get the first 6?
Note: the roll of the 6 is included in the "number of throws before we get the first 6."
\(\text{}\)
2. Extension of the summation method
\(\text{}\)
Evaluate \(\displaystyle\sum_{i=1}^\infty \frac{ i^2} { 2^i } \).
If we had to describe this summation, we would call it a "quadratic-geometric progression", because the numerator is a quadratic \( i^2 \). We will use a different approach to reduce this to a "linear-geometric progression", which is an AGP.
Let the sum be \(S,\) then since the common ratio is \( \frac{1}{2} \), we will multiply \(S\) by \( \frac{1}{2} .\) Subtracting \(\frac{1}{2}S\) from \(S\) gives
\[ \begin{array} { r lllllll}
S& =\frac 12 & +\frac {4}{4} & +\frac{9}{8} &+\frac{16}{16} &+\frac{25}{32} &+\cdots \\ \frac{1}{2} S& = & + \frac 14 & +\frac {4}{8} & +\frac{9}{16} &+\frac{16}{32} &+\cdots \\ \hline \frac{1}{2} S & =\frac 12 & +\frac {3}{4} & +\frac{5}{8} &+\frac{7}{16} &+\frac{9}{32} &+\cdots .\\ \end{array} \]We may recognize the AGP here, but let \(T=\frac{1}{2} S\) and continue with this procedure of taking the difference:
\[ \begin{array} { r lllllll}
T & =\frac 12 & +\frac {3}{4} & +\frac{5}{8} &+\frac{7}{16} &+\frac{9}{32} &+\cdots \\
\frac{1}{2} T & = & + \frac 14 & +\frac {3}{8} & +\frac{5}{16} &+\frac{7}{32} &+\cdots \\
\hline \frac{1}{2} T & = \frac{1}{2} & + \frac{2}{4} & + \frac{2}{8} & + \frac{2}{16} & + \frac{2}{32} & + \cdots .\\ \end{array} \]Now, observe that with the exception of the first term, we get a GP with initial term \( \frac{2}{4} \) and common ratio \( \frac{1}{2} \). As it turns out, the first term would often not fit into the pattern of the sequence, and we just got lucky previously. We thus get
\[ \frac{1}{2} T = \frac{1}{2} + \frac{ \frac{2}{4} } { 1 - \frac{1}{2} } = \frac{1}{2} + 1 = \frac{3}{2} . \]
Therefore, \( T = 3 ,\) which implies \( S = 2T = 6. \ _\square \)
Observe that when we take the difference of terms in a quadratic sequence, we will end up with a linear sequence. This holds more generally: When we take the difference of terms in a degree \(n\) sequence, we will get a degree \(n-1 \) sequence. This is explored in detail in Method of Differences. We will use this idea repeatedly, to work with such "polynomial-geometric progression."
Evaluate \(\displaystyle\sum_{i=1}^\infty \frac{ i^3} { 3^i } \).
Observe that we have a "cubic-geometric progression" with common ratio \( \frac{1}{3} \). Let's multiply by \( \frac{1}{3} \) and take the difference:
\[ \begin{array} { r lllll}
S & = \frac{1}{3} & + \frac{8}{9} & + \frac{ 27}{27} & + \frac{ 64}{ 81} & + \frac{ 125}{243} & + \cdots \\ \frac{1}{3} S & = & + \frac{1}{9} & + \frac{8}{27} & + \frac{ 27}{81} & + \frac{ 64}{ 243} & + \cdots \\ \hline \frac{2}{3} S & = \frac{1}{3} & + \frac{7}{9} & + \frac{ 19}{27} & + \frac{ 37}{ 81} & + \frac{ 61}{243} & + \cdots. \\ \end{array} \]We thus get \( \frac{2}{3} S - \frac{1}{3} =\displaystyle \sum_{i=1}^\infty \frac{ 3i^2+3i+1}{3^{i+1} } \), which is a "quadratic-geometric progression". Set this to be \(T\). Then multiplying by \( \frac{1}{3} \) and taking the difference gives
\[ \begin{array} { r lllll}
T & = \frac{7}{9} & + \frac{ 19}{27} & + \frac{ 37}{ 81} & + \frac{ 61}{243} & + \cdots \\ \frac{1}{3} T & = & + \frac{7}{27} & + \frac{ 19}{81} & + \frac{ 37}{ 243} & + \cdots \\ \hline \frac{2}{3} T & = \frac{7}{9} & + \frac{12}{27} & + \frac{ 18}{81} & + \frac{24}{243} & + \cdots. \\ \end{array} \]We thus get \( \frac{2}{3} T - \frac{7}{9} =\displaystyle \sum_{i=1}^\infty \frac{ 6(i+1)} { 3^{i+2}} \), which is a "linear-geometric progression. Set this to be \( U \). Then multiplying by \( \frac{1}{3} \) and taking the difference gives
\[ \begin{array} { r lllll}
U & = \frac{12}{27} & + \frac{ 18}{81} & + \frac{24}{243} & + \cdots \\
\frac{1}{3} U & = & + \frac{12}{81} & + \frac{ 18}{342} & + + \cdots \\
\hline
\frac{2}{3} U & = \frac{12}{27} & + \frac{6}{81} & + \frac{6}{ 243} & + \cdots. \\ \end{array} \]We then get \( \frac{2}{3} U - \frac{12}{27} = \displaystyle \sum_{i=1}^\infty \frac{6}{3^{i+3} } ,\) which is a geometric progression with an infinite sum of \( \frac{ \frac{6}{81} } { 1 - \frac{1}{3} } = \frac{1}{9} \).
This gives us
\[\begin{align} \frac{2}{3} U &= \frac{12}{27} + \frac{1}{9} &&\Rightarrow U = \frac{5}{6} \\ \frac{2}{3} T &= \frac{7}{9} + \frac{5}{6} &&\Rightarrow T = \frac{29}{12} \\ \frac{2}{3} S &= \frac{1}{3} + \frac{29}{12} &&\Rightarrow S = \frac{33}{8}. \ _\square \end{align}\]
Now, you're ready to solve the following problems on your own. Good luck!
\[W=2+5x+9x^2+14x^3+20x^4+\cdots \]
Given \(|x|<1\), find the value of the series \(W\).
Clarification: \(2,5,9,14,20,\ldots\) follows a \(2^{\text{nd}}\)-degree polynomial function, i.e. their second finite difference is a constant.
\[ \dfrac{\color{magenta}{1^2}}{\color{indigo}{1}}+\dfrac{\color{magenta}{5^2}}{\color{indigo}{11}}+\dfrac{\color{magenta}{9^2}}{\color{indigo}{(11)^2}}+\dfrac{\color{magenta}{13^2}}{\color{indigo}{(11)^3}}+\dfrac{\color{magenta}{17^2}}{\color{indigo}{(11)^4}}+\cdots= \, ?\]
\[ S = 0.1 + 0.02 + 0.003 + 0.0004 + \cdots + \dfrac n{10^n} + \cdots \]
Given that the infinite sum \( S\) can be expressed as \( \frac ab\), where \(a\) and \(b\) are coprime positive integers, find \(a+b\).
See Also
To enhance your problem solving skills on arithmetic progressions, geometric progressions, and arithmetic-geometric progression, you can check out the following wikis: