Finding a formula for the sequence $ 2, 4, 10, 28, 82, \dots $

Question

I have the scenario where I start at $2$ and then multiply the previous by $3$ and then subtract by $2$. For example $$ 2, 4, 10, 28, 82, \dots $$

I tried to look at the pattern of how much they are increasing by: $$ 2, 6, 18, 54, \dots $$ which multiplied by $3$, but I don't know how that translate to a function. When writing it out, I get $2 \cdot 3^{\mathrm{term}-1}$, an amount that I'm not sure how to express. Just $2 \cdot 3^{\mathrm{term}-1} - 2 \cdot 3^{\mathrm{term}-2} - \cdots$ until you subtract $2 \cdot 3^0$.

Answer 1

Denote the $n$-th term by $a_n$ with $n\geq 0$, we have

$a_0=2$,

$a_1=3\times 2-2=2\times (3-1)$,

$a_2=3\times2\times(3-1)-2=2\times(3^2-3-1)$,

...

$a_n=2\times(3^n-\sum_{k=0}^{n-1} 3^{k})$,

where, as the sum of a geometric series, $\sum_{k=0}^{n-1} 3^{k}=\frac{3^n-1}{2}$. Thus finally,

$a_n=3 a_{n-1}-2=2\times(3^n-\frac{3^n-1}{2})=3^n+1$.

Denote the difference between two adjacent terms by $d_n$ for $n\geq 1$, we have

$d_n=a_n-a_{n-1}=3^n-3^{n-1}=3^{n-1}\times(3-1)= 2\times3^{n-1}=3 d_{n-1}$.

Answer 2

So when you have a sequence whose first differences form a geometric sequence — as this one does, as you've noted, with the formula for the $n^{th}$ term being $2\cdot3^n$, $n\ge1$ — the explicit formula for the terms of the original sequence is almost certain to have the form $r^n+d$, for some numbers $r$ and $d$. As noted in the comments and in the other answer, this is indeed the case for your sequence; if by $a_n$ you denote the $n^{th}$ term of your sequence (with $n\ge0$), you have that $a_n=3^n+1$. My goal here is to show you one way of arriving at this answer, via a very powerful and widely-applicable method known as generating functions.

Generating Functions — What Are They?

You're familiar with power series, I hope? If not, they refer to a type of infinite summation, specifically ones of the form $\sum_{n=0}^{\infty}c_nx^n$, where the $c_n$'s are elements taken from a field or a ring (in this case, the $c_n$'s are real numbers). In many cases, these infinite sums are evaluated by substituting an appropriate value for $x$; such examples are the power series representation of $\sin x$, $\cos x$ and $e^x$, and many others. The ability to make such substitutions and reach a numerically sensible result is a property of analytic series called convergence; whether or not a power series converges is completely determined by the $c_n$'s. A power series that does converge for appropriate values of $x$ can be properly called a function of $x$.

My point in explaining this, as you may anticipate, is that there exist power series which are not convergent; in fact, most of them are not. If a real number is substituted for $x$ in such a series, one will not get a real-valued result, and so this kind of power series cannot be called functions of $x$. As you may guess, generating functions often fall into this category. Not always — there are some generating functions that can be considered functions for appropriately small values of $x$ — but many do. Why, then, do we call them generating functions?

The answer to this is that power series can also be considered as vehicles for the coefficients $c_n$ themselves, indexed by powers of $x$; a commonly-used analogy is that they act as a "clothesline" on which the sequence of $c_n$'s are hung. $x$ is no more than a dummy variable in this scenario; to extend the analogy, the $x^n$'s act as the "pegs" fastening the $c_n$'s to the clothesline. By treating power series in this way, as purely algebraic objects with no regard for convergence, we hope to find a form for the generating functions in terms of $x$ that will allow us to efficiently compute whatever coefficients we need.

Generating Functions — The Method (worked example)

I will now demonstrate the basic method of generating functions using the question you've posted. The first step is to define the generating function. Let $A(x)=\sum_{n=0}^{\infty}a_nx^n=a_0+a_1x+a_2x^2+...$ be the generating function for your sequence, with $a_0=2$. Now take a look at the recurrence for your sequence, which is:

$$a_{n+1}=3a_n-2, n\ge0, a_0=2$$

Our goal is to use multiplication by $x^n$ and summation to transform this into an equation of power series, and to relate them to $A(x)$. Begin by multiplying through by $x^n$ and summing over all values of $n$ for which the recurrence is valid (which is all $n$ greater than or equal to $0$, remember). If you do this, what you get is the following:

$$\sum_{n=0}^{\infty}a_{n+1}x^n=\sum_{n=0}^{\infty}3a_nx^n-\sum_{n=0}^{\infty}2x^n$$

Let us examine each term separately and see how we can relate them to $A(x)$. Beginning on the left with $\sum_{n=0}^{\infty}a_{n+1}x^n$, we take a look at the first few terms. What we see is $a_1+a_2x+a_3x^2+a_4x^3+...$

Compare this to the expansion of $A(x)$. It's almost the same, isn't it? Sure, $a_0$ is missing, and it looks like each $a_n$ is off by $1$ in terms of which $x^n$ they're paired with, but otherwise they are very, very similar. Now think: given the expansion of $A(x)$, how can we modify it to fit the expansion of this term? Obviously, we'd need to subtract $a_0$, and the mismatch between the $a_n$'s and $x^n$'s can be accounted for by dividing the resulting expression by $x$. To put it in symbols, we find that $\sum_{n=0}^{\infty}a_{n+1}x^n=\frac{A(x)-a_0}{x}$.

That takes care of the first term. The next one is much easier. We have $\sum_{n=0}^{\infty}3a_nx^n$; by the rules governing summation (which apply even when dealing with divergent sums), we are allowed to move the constant coefficient $3$ outside the sum, so that we have $3\sum_{n=0}^{\infty}a_nx^n$. If we expand what's left inside, we see that we have $a_0+a_1x+a_2x^2+a_3x^3+...$, which is exactly equal to $A(x)$! Therefore, we have $\sum_{n=0}^{\infty}3a_nx^n=3A(x)$.

Now for the last term. Just as with the previous term, the $2$ in $\sum_{n=0}^{\infty}2x^n$ can be moved outside the sum, so that we have $2\sum_{n=0}^{\infty}x^n$. Expanding what remains inside, we get $1+x+x^2+x^3+x^4+x^5+x^6...$.

This is a very fundamental series; if you don't know about it yet, now's the time to learn it. I'll leave it to you to research it; I just want to point out that it has a very well-known closed form, which is $\frac{1}{1-x}$. Since we have $2\sum_{n=0}^{\infty}x^n$, we end up with $\sum_{n=0}^{\infty}2x^n=\frac{2}{1-x}$.

Nearly there! The last step in the method is to substitute the closed-form expressions we found in the previous steps for their power series equivalents in our modified recurrence relation. Remember, we had the following:

$$\sum_{n=0}^{\infty}a_{n+1}x^n=\sum_{n=0}^{\infty}3a_nx^n-\sum_{n=0}^{\infty}2x^n$$.

Making the substitutions, we get the following:

$$\frac{A(x)-a_0}{x}=3A(x)-\frac{2}{1-x}$$.

Now it's a matter of solving for $A(x)$. Begin by multiplying through by $x$, so that we have $A(x)-a_0=3xA(x)-\frac{2x}{1-x}$. Next, subtract $3xA(x)$ and add $a_0$; we get $A(x)-3xA(x)=\frac{a_0-(a_0+2)x}{1-x}$.

As you can see, I took the liberty of combining the fractions on the right and simplifying. Next, factor $A(x)$ on the left: $A(x)(1-3x)=\frac{a_0-(a_0+2)x}{1-x}$. Divide through by $1-3x$ and substitute the given value of $2$ for $a_0$: $A(x)=\frac{2-4x}{(1-3x)(1-x)}$.

And that concludes the method! Were you to expand the expression on the right (whether by hand or by a CAS such as WolframAlpha), you would find that the coefficient $a_n$ of $x^n$ is the $n^{th}$ term of your sequence, for all values of $n$. Now the "function" part of "generating function" makes more sense: though you cannot plug in an $x$ value into $A(x)$ and get back a coefficient/term of the sequence, it is true that for each value of $n$, there is one and only one coefficient of $x^n$; thus this can be considered a function of $n$.

Of course, we don't see any dependence on $n$ in the final form of the generating function, which makes it seem pretty useless, right? How are we supposed to find the $n^{th}$ coefficient without writing out the expansion in its entirety? Answering this question is known as coefficient extraction. There are a few ways to go about it; the one I will be showing you today makes use of partial fractions and the extended binomial theorem. Regarding notation, the operation of finding the $n^{th}$ coefficient in the expansion of $A(x)$ is denoted by $[x^n]A(x)$. Remember that, because I'll be using it a lot.

To get started, we'd like to break up $\frac{2-4x}{(1-3x)(1-x)}$ into separate terms. Suppose that it can be written as $\frac{A}{1-3x}+\frac{B}{1-x}$ for some numbers $A$ and $B$. Following the usual rules of fraction addition, our numerator in this case would be $A(1-x)+B(1-3x)$. Expanding and regrouping, we reshuffle our numerator to be $(A+B)-x(A+3B)$. Now compare this to our actual numerator, which is $2-4x$. We can construct a system of equations, specifically $A+B=2$ and $A+3B=4$. Solve this any way you like; you'll find that $A=B=1$, which means that we have a new form for $A(x)$: $A(x) = \frac{1}{1-3x}+\frac{1}{1-x}$.

Now what? There are still no $n$'s anywhere; it seems that we've just traded the problem of extracting coefficients of one series for the extraction of coefficients of two series; this feels more like a step backwards than anything!

Enter the extended binomial theorem. This is another topic you will definitely want to do some deep learning on; for now I'll just give you the summary as it pertains to the problem. Given an expression of the form $\frac{1}{(1-\alpha x)^s}$, $[x^k]\frac{1}{(1-\alpha x)^s}=\binom{s+k-1}{k}(\alpha)^k$. This can be extended further as follows:

$$[x^k](\frac{1}{(1-\alpha x)^s}+\frac{1}{(1-\beta x)^r})=[x^k]\frac{1}{(1-\alpha x)^s}+[x^k]\frac{1}{(1-\beta x)^r} = \binom{s+k-1}{k}(\alpha)^k+\binom{r+k-1}{k}(\beta)^k$$

This is exactly what we need to finish off the problem. Take the first term of $A(x)$ and note that it can be written as $\frac{1}{(1-3x)^1}$; matching it with the expression in the first part of the extended binomial theorem, we see that $s=1$ and $\alpha=3$. The contribution of this term to the coefficient of $x^n$ of $A(x)$ is therefore $\binom{1+n-1}{n}3^n=\binom{n}{n}3^n$. $\binom{n}{n}=1$ for all values of $n$, so this reduces to $3^n$. Now take the second term, $\frac{1}{(1-x)^1}$. Again, $s=1$, but now we have $\alpha=1$, so the contribution to $a_n$ by this term is $\binom{1+n-1}{n}1^n = \binom{n}{n}1^n=1^{n+1}$. $1^{n+1}=1$ for all natural values of $n$. By the second part of the theorem, the overall value of $a_n$ is equal to the sum of these, allowing us to finally conclude that $a_n=3^n+1$ — as per the other answers!

I hope that this demonstrates the utility of generating functions. It may have seemed like a lot of work for a comparatively easy problem, but you'll be really well served if you can get your head around the concept. Generating functions are incredibly powerful with many, many applications, from probability to number theory and most things in between. Put simply: they rock!

Homework For You

• read up on generating functions. There are many resources available online; the one that strikes the best balance between comprehensiveness and accessibility, in my opinion, is the free e-book "generatingfunctionology" by Herbert Wilf (you'll see his name a lot when searching for resources)

• go over my derivation, and keep going over it until you understand it completely (best done with Wilf's excellent book at hand). Then come up with a few practise problems on your own and solve them

• bone up on the extended binomial theorem, do some practise problems

Answer 3

Assuming that you are familiar with recurrence relations, we can translate your words directly into a recurrence relation as follows

$$ a_n=3a_{n-1}-2, \quad a_0=2 $$

The first step is to eliminate the inhomogeneous term, so assume that $a_n=b_n+B$ to get

$$ b_n+B=3(b_{n-1}+B)-2 $$

and choose $B=1$, leaving us with

$$ b_n=3b_{n-1}\\ b_n=b_03^n\\ b_0=a_0-1=1\\ $$

And finally

$$ a_n=(a_0-1)3^n+1=3^n+1 $$