1
$\begingroup$

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.

$\endgroup$

closed as off-topic by user21820, Shaun, Javi, Adrian Keister, José Carlos Santos Apr 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.

  • $\begingroup$ 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. $\endgroup$ – Malcolm Oct 16 '18 at 22:03
1
$\begingroup$

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}

$\endgroup$
  • 3
    $\begingroup$ It would be nice to see a fool-proof algorithm for someone who didn’t recognize the pattern. $\endgroup$ – gen-z ready to perish Oct 16 '18 at 22:30
  • $\begingroup$ @ChaseRyanTaylor as you wish :) $\endgroup$ – Rhys Hughes Oct 16 '18 at 22:48
  • $\begingroup$ 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!! $\endgroup$ – gen-z ready to perish Oct 17 '18 at 6:02
2
$\begingroup$

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})$$

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.