# Derive explicit formula for sequence $x_{n+1}=3x_n+2$ [closed]

Define a sequence $$(x_n)_{n=1}^\infty$$ by $$\begin{cases} x_1 = 2 \\ x_{n+1} = 3x_n + 2 & n\ge1 \end{cases}$$ Determine an explicit formula for $$x_n$$ (i.e., an explicit expression for $$x_n$$ in terms of $$n$$ that does not involve previous terms in the sequence).

I wasn't exactly sure how to go about this. If anyone could give me hint on how to start that would be greatly appreciated.

## closed as off-topic by user21820, Shaun, Javi, Adrian Keister, José Carlos SantosApr 8 at 14:20

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – user21820, Shaun, Javi, Adrian Keister, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.

• The multiplication by $3$ leads me to think that powers of $3$ may be involved. I would write out a few terms, look at them with powers of $3$ in mind, conjecture a formula, then prove it. – Malcolm Oct 16 '18 at 22:03

Taking the first few values of $$x_{n+1} = 3 \, x_{n} + 2$$, $$x_{1} = 2$$, leads to $$x_{n} \in \{ 2, 8, 26, 80, 242, \cdots \}.$$ This pattern is easily recognizable by considering powers of $$3$$. From this it is concluded that $$x_{n} = 3^{n} -1$$.

To check this consider: $$3 x_{n} + 2 = 3^{n+1} - 3 + 2 = 3^{n+1} - 1 = x_{n+1}.$$

Alternate method: Use of exponential generating function. Let $$\phi(t) = \sum_{k=1}^{\infty} x_{k} \, \frac{t^{k}}{k!}$$ be the exponential generating function for this sequence. Now, \begin{align} \sum_{k=1}^{\infty} x_{k+1} \, \frac{(k+1) \, t^{k}}{(k+1)!} &= 3 \, \sum_{k=1}^{\infty} x_{k} \, \frac{t^{k}}{k!} + 2 \, \sum_{k=1}^{\infty} \frac{t^{k}}{k!} \\ \frac{d}{dt} \, \left(\phi - x_{1} \, t \right) &= 3 \, \phi - 2 \, e^{t} \\ \phi' - 3 \, \phi &= 2 \, e^{t}. \end{align} The solution of this first order differential equation is $$\phi(t) = e^{3 t} - e^{t}$$ and leads to the result \begin{align} \sum_{k=1}^{\infty} x_{k} \, \frac{t^{k}}{k!} &= \sum_{k=1}^{\infty} (3^{k} - 1) \, \frac{t^{k}}{k!} \\ x_{k} &= 3^{k} - 1. \end{align}

• It would be nice to see a fool-proof algorithm for someone who didn’t recognize the pattern. – let's have a breakdown Oct 16 '18 at 22:30
• @ChaseRyanTaylor as you wish :) – Rhys Hughes Oct 16 '18 at 22:48
• That’s actually a really awesome technique! I see why you didn’t post it at first (it’s definitely overkill) but it’s so cool to have seen it!! – let's have a breakdown Oct 17 '18 at 6:02

We are given $$x_1=2$$.

Then: $$x_2=3(2)+2=(3+1)(2)$$ $$x_3=3(3(2)+2)+2=3^2(2)+(3)(2)+2=(3^2+3+1)(2)$$ It follows fairly easily that $$x_4=(3^3+3^2+3+1)(2)$$ and so we have $$x_n=2\sum_{k=0}^{n-1}{3^k}$$

This can be equated to the $$x_n=3^n-1$$ that Leucippus achieved by using the identity: $$x^n-1\equiv(x-1)(1+x+...+x^{n-1})$$

Note that the sequence $$\left\{y_n\right\}_{n\in\mathbb{Z}_{>0}}$$ given by $$y_n:=x_n+1$$ for $$n=1,2,3,\ldots$$ satisfies $$y_1=3$$ and $$y_{n+1}=3\,y_n$$ for each integer $$n\geq 1$$. Thus, by induction, $$y_n=3^{n}$$ and so $$x_n=3^n-1$$ for every positive integer $$n$$.