Method of Differences

Introduction

The method of differences is a mathematical technique used to simplify the process of summing a series when the consecutive terms of the series have a recognizable pattern in their differences. The main idea is to express each term as the difference between two consecutive terms of a secondary sequence. If the difference between consecutive terms of the original series results in a known series, such as an arithmetic progression (AP) or a geometric progression (GP), this method can be particularly effective.

When the differences are not readily apparent, the method can be extended to second differences, third differences, and so forth, until a known series is identified. The sequence of differences is expected to be simpler than the original sequence and ideally should converge to a series that is easily summable.

For example: The sequence (\( u_n \)):\

\[ 2, \quad 7, \quad 17, \quad 36, \quad \ldots \]

First difference (\( \Delta u_n \)) is:

\[ \quad 5, \quad 10, \quad 19, \quad \ldots \]

Second difference (\( \Delta^2 u_n \)) is: (observe the delta notation that is used to denote differences)

\[ \quad\quad 5, \quad 9, \quad 13, \quad \ldots \]

Applying method of differences

When differences are in AP

Example

Problem:

Given the series \(3, 8, 18, 33, 53, 78, 108, \ldots\), find the \( n \)-th term, denoted as \( t_n \). Also find the sum \(S_n\) upto \(n\) terms.

Solution:

Consider the series:

\[ S = 3 + 8 + 18 + 33 + 53 + 78 + 108 + \ldots + t_n \]

Rewrite the series by shifting one term to the right:

\[\begin{align} S &= 3 + &8 + &18 + &33 + &53 + &78 + &108 + \ldots + &t_n +&0\\ S &= &3 + &8 + &18 + &33 + &53 + &78 + \ldots + &t_{n-1} + &t_n \end{align}\]

Subtract the second series from the first:

\[ 0 = 3 + (8 - 3) + (18 - 8) + (33 - 18) + (53 - 33) + (78 - 53) + (108 - 78) + \ldots + (t_n - t_{n-1}) -t_n\]

This simplifies to:

\[ 0 = 3 + 5 + 10 + 15 + 20 + 25 + 35 + \ldots + t' - t_n \]

where \(t'=t_n-t_{n-1}\). We don't know what \(t_n\) and \(t_{n-1}\) are.

Bringing \( t_n \) to the left side, we get:

\[ t_n = 3 + 5 + 10 + 15 + 20 + 25 + 35 + \ldots + t' \]

From 5 onward, the series is an arithmetic progression (AP) with the first term \( a = 5 \) and common difference \( d = 5 \). The term \( 3 \) is separate from this AP.

The sum of an AP is given by the formula \( \text{Sum} = \frac{n}{2}(2a + (n - 1)d) \), where \( n \) is the number of terms. However, in this series, we consider the AP from the second term onward; hence, we subtract 3 from the sum to account for the initial term not being part of the AP. Also from 5 to the last term we have \(n-1\) terms in AP.

Thus, the \( n \)-th term of the original series, \( t_n \), can be found by summing the AP from 5 to the last term and then adding 3 to that sum:

\[ t_n = 3 + \frac{n-1}{2}[2 \cdot 5 + (n - 2) \cdot 5] \]

Simplifying, we get:

\[ t_n = 3 + \frac{n-1}{2}(10 + 5n - 10) \]

\[ t_n = 3 + \frac{5n(n-1)}{2} \]

This is the formula for the \( n \)-th term of the given series.

We can write t_k as:

\[ t_k = 3 + \frac{5k(k-1)}{2} = 3 + \frac{5}{2}k^2 - \frac{5}{2}k \]

\[ = \frac{5k^2}{2} - \frac{5k}{2} + 3 \]

For the sum \( S_n = \sum_{k=1}^{n} t_k \), distribute the sum:

\[ S_n = \sum_{k=1}^{n} \frac{5k^2}{2} - \sum_{k=1}^{n} \frac{5k}{2} + \sum_{k=1}^{n} 3 \]

Using the formulas for the sum of squares \(\sum k^2 = \frac{n(n + 1)(2n + 1)}{6}\), the sum of the first \( n \) natural numbers \(\sum k = \frac{n(n + 1)}{2}\), and the sum of a constant \( n \) times:

\[ S_n = \frac{5}{2} \cdot \frac{n(n + 1)(2n + 1)}{6} - \frac{5}{2} \cdot \frac{n(n + 1)}{2} + n \cdot 3 \]

\[ S_n = \frac{5n(n + 1)(2n + 1)}{12} - \frac{5n(n + 1)}{4} + 3n \]

Taking \( n(n + 1) \) common from the first two terms and simplifying:

\[ S_n = n(n + 1) \left( \frac{5(2n + 1)}{12} - \frac{5}{4} \right) + 3n \]

\[ S_n = n(n + 1) \left( \frac{5(2n + 1) - 15}{12} \right) + 3n \]

\[ S_n = n(n + 1) \left( \frac{10n - 10}{12} \right) + 3n \]

\[ S_n = \frac{5n(n + 1)(n - 1)}{6} + 3n \]

Taking \( n \) common from both terms:

\[ S_n = n \left( \frac{5(n + 1)(n - 1)}{6} + 3 \right) \]

\[ \implies S_n = n \left( \frac{5(n^2 - 1) + 18}{6} \right) \]

\[ \implies S_n = n \left( \frac{5n^2 + 13}{6} \right) \]

\[ \implies S_n = \frac{n(5n^2 + 13)}{6} \]

As you can observe from the above example, this is a very tedious process.

We observe that:

When a sequence has constant first differences, its nth term is given by \( t_n = an + b \), which is a linear relationship.

If the sequence has constant second differences, the nth term follows a quadratic relationship, expressed as \( t_n = an^2 + bn + c \).

For sequences with constant third differences, the relationship becomes cubic, and the nth term can be represented as \( t_n = an^3 + bn^2 + cn + d \).

In general, if the \( k \)-th differences of a sequence are constant, the nth term of the sequence, \( t_n \), is given by a polynomial of degree \( k \). This means that the highest power of \( n \) in the term's formula will be \( n^k \).

The only problem left is determining coefficients of these polynomials. Since we already know \(t_1\), \(t_2\), \(t_3\), .... we can form a sufficient number of equations to find coefficients. Consider the example considered before.

Example

Problem: Given the series \(3, 8, 18, 33, 53, 78, 108, \ldots\), find the \( n \)-th term.

Solution:

Given the series: \(3, 8, 18, 33, 53, 78, 108, \ldots\) First differences:

\(8 - 3 = 5\)

\(18 - 8 = 10\)

\(33 - 18 = 15\)

\(53 - 33 = 20\)

\(78 - 53 = 25\)

Second differences:

\(10 - 5 = 5\)

\(15 - 10 = 5\)

\(20 - 15 = 5\)

\(25 - 20 = 5\)

The second differences are constant, which suggests a quadratic \( n \)-th term of the form \( t_n = an^2 + bn + c \).

Using the given terms to set up equations:

For \( n = 1 \): \( t_1 = 3 = a(1)^2 + b(1) + c \)

For \( n = 2 \): \( t_2 = 8 = a(2)^2 + b(2) + c \)

For \( n = 3 \): \( t_3 = 18 = a(3)^2 + b(3) + c \)

This gives us the system of equations:

1. \( a + b + c = 3 \)
2. \( 4a + 2b + c = 8 \)
3. \( 9a + 3b + c = 18 \)

Solving this system of equations for \( a \), \( b \), and \( c \) gives us the coefficients for the quadratic \( n \)-th term formula.

The solution to the system of equations is \( a = \frac{5}{2} \), \( b = -\frac{5}{2} \), and \( c = 3 \).

Therefore, the \( n \)-th term \( t_n \) of the series is given by:

\[ t_n = \frac{5}{2}n^2 - \frac{5}{2}n + 3 \]

We can even make this faster by assuming the n-th term as \(t_n = a(n-1)(n-2)+b(n-1)+c\)

Using the form \( t_n = a(n-1)(n-2) + b(n-1) + c \), we can determine the coefficients \( a \), \( b \), and \( c \) using the given terms \( t_1 = 3 \), \( t_2 = 8 \), and \( t_3 = 18 \).

For \( t_1 = 3 \) (when \( n = 1 \)):

\[ t_1 = a(1-1)(1-2) + b(1-1) + c = c \]

For \( t_2 = 8 \) (when \( n = 2 \)):

\[ t_2 = a(2-1)(2-2) + b(2-1) + c = b + c \]

For \( t_3 = 18 \) (when \( n = 3 \)):

\[ t_3 = a(3-1)(3-2) + b(3-1) + c = 2a + 2b + c \]

Now we have the system of equations: 1. \( c = 3 \) 2. \( b + c = 8 \) 3. \( 2a + 2b + c = 18 \)

Using these equations, we can find the values of \( a \), \( b \), and \( c \). Since we already know that \( c = 3 \), we can substitute it into the other equations to find \( b \) and \( a \).

The solution to the system of equations is \( a = \frac{5}{2} \), \( b = 5 \), and \( c = 3 \).

Therefore, the \( n \)-th term \( t_n \) of the series is given by:

\[ t_n = \frac{5}{2}(n-1)(n-2) + 5(n-1) + 3 \]

Info

If the second difference of a sequence is constant, then the \( n \)-th term \( t_n \) can be assumed to be of the form:

\[ t_n = a(n-1)(n-2) + b(n-1) + c \]

This form is derived from the general form of a quadratic equation, with \( a \), \( b \), and \( c \) as coefficients that can be determined by the initial terms of the sequence.

Similarly, if the third difference of a sequence is constant, the \( n \)-th term \( t_n \) takes on the form of a cubic equation and can be assumed to be:

\[ t_n = a(n-1)(n-2)(n-3) + b(n-1)(n-2) + c(n-1) + d \]

In this form, \( a \), \( b \), \( c \), and \( d \) are coefficients that define the sequence and can be calculated using the known terms of the sequence.

By employing these assumptions for quadratic or cubic sequences, respectively, the process of finding the specific coefficients—and thus the formula for \( t_n \)—becomes more direct and efficient.

When differences are in GP

Example

Problem:

Given the sequence \(2, 5, 14, 41, 122, \ldots\),

1. Derive the general formula for the \(n\)-th term of the sequence, denoted as \(t_n\).
2. Determine the formula for the sum of the first \(n\) terms of this sequence, represented as \(S_n\).

Solution:

Given the sequence \(2, 5, 14, 41, 122, \ldots\), we notice that the first differences form a geometric progression (GP) with a common ratio of 3. The first term of the GP is 3.

We can express the sum \( S_n \) of the first \( n \) terms of the sequence and then write it again shifted by one term to the right, in order to find a formula for \( t_n \):

\[\begin{align} S_n &= 2 + 5 + 14 + 41 + 122 + \ldots \phantom{t_{n-1}} + t_n \\ S_n &=\quad \quad 2 + 5 + 14 + 41 + \ldots \phantom{+t_n-2} + t_{n-1} + t_n \\ \end{align}\]

Subtracting the second series from the first, aligning the terms visually, we get:

\[ 0 = 2 + (5 - 2) + (14 - 5) + (41 - 14) + (122 - 41) + \ldots + (t_n - t_{n-1}) - t_n \]

This simplifies to:

\[ 0 = 2 + 3 + 9 + 27 + \ldots + (t_n - t_{n-1}) -t_n \]

Bringing \( t_n \) to one side:

\[ t_n = 2 + 3 + 9 + 27 + \ldots + (t_n - t_{n-1}) \]

The right side, excluding the \( 2 \), is a GP starting with \( 3 \) and ending with \( t_n - t_{n-1} \). The sum of a GP is given by:

\[ S = a \frac{r^n - 1}{r - 1} \]

Where \( a \) is the first term, \( r \) is the common ratio, and \( n \) is the number of terms.

The nth term \( t_n \) is thus:

\[ t_n = 2 + 3 \frac{(3^{n-1} - 1)}{3 - 1} \]

Simplifying, we get:

\[\begin{align} t_n &= 2 + 3 \left(\frac{3^{n-1} - 1}{2}\right) \\ t_n &= 2 + \frac{3}{2}(3^{n-1} - 1) \\ t_n &= 2 + \frac{3^n - 3}{2} \\ t_n &= 2 + \frac{3^n}{2} - \frac{3}{2} \\ t_n &= \frac{3^n + 1}{2} \end{align}\]

Given the formula for the nth term \( t_n = \frac{3^n + 1}{2} \), the sum \( S_n \) of the first \( n \) terms of the sequence is the summation of \( t_r \) from \( r = 1 \) to \( n \):

\[ S_n = \sum_{r=1}^{n} \frac{3^r + 1}{2} \]

The sum \( S_n \) will be the sum of two separate series: one for the geometric part and one for the constant part:

\[ S_n = \sum_{r=1}^{n} \frac{3^r}{2} + \sum_{r=1}^{n} \frac{1}{2} \]

For the geometric series part, the sum is:

\[ \sum_{r=1}^{n} \frac{3^r}{2} = \frac{1}{2} \left( \frac{3(3^n - 1)}{3 - 1} \right) \]

For the constant series part, the sum is simply:

\[ \sum_{r=1}^{n} \frac{1}{2} = \frac{n}{2} \]

Combining these gives the total sum:

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

This expression represents the sum of the first \( n \) terms of the given sequence.

Again, we need not apply the long tedious process. We can follow the following rules to find the genral term:

Rules

When a sequence's first differences form a geometric progression with common ratio \( r \), the general term of the sequence can be represented as \( t_n = ar^{n-1} + b \).

If the sequence's second differences form a geometric progression with the same common ratio \( r \), the general term is given by \( t_n = ar^{n-1} + bn + c \).

For sequences where the third differences are also a geometric progression with common ratio \( r \), the general term can be assumed to be \( t_n = ar^{n-1} + bn^2 + cn + d \).

To determine the coefficients \( a, b, c, d, \ldots \) in the expressions for the general term \( t_n \) when the differences form a geometric progression, you typically use the initial terms of the sequence. Here’s a step-by-step approach:

1. For \( t_n = ar^n + b \):

   • Substitute \( n = 1 \) into the equation using the first term of the sequence to find an equation involving \( a \) and \( b \).
   • Substitute \( n = 2 \) to find a second equation.
   • Solve the system of equations to find \( a \) and \( b \).

2. For \( t_n = ar^n + bn + c \):

   • Again, use the terms of the sequence, substituting \( n = 1, 2, \) and \( 3 \) to create three equations.
   • This will yield a system of three equations with three unknowns.
   • Solve this system to find the values of \( a, b, \) and \( c \).

3. For \( t_n = ar^n + bn^2 + cn + d \):

   • Use the first four terms of the sequence, substituting \( n = 1, 2, 3, \) and \( 4 \) to generate four equations.
   • This system of four equations can then be solved for \( a, b, c, \) and \( d \).