Find recursive formula for sequence $a_n = \left(\frac23\right)^n + n$

Question

So I start with: $$a_n = \left(\frac23\right)^n + n$$
I know $a_1=\frac53, a_2=\frac{22}9, a_3=\frac{340}{81}, a_4=\frac{1247}{243} $ Then I do: $$a_{n-1} = \left(\frac23\right)^{n-1} + (n-1)$$

Do I now do $a_n - a_{n-1}$ or $a_n\over a_{n-1}$ ?

Answer 1

I think you are right to try and find $a_n-a_{n-1}$. If we work it out, then we have $$a_n-a_{n-1}=\big(\frac{2}{3}\big)^n-\big(\frac{2}{3}\big)^{n-1}+n-n+1$$ $$a_n-a_{n-1}=\frac{2}{3}\big(\frac{2}{3}\big)^{n-1}-\big(\frac{2}{3}\big)^{n-1}+1$$ $$a_n-a_{n-1}=-\frac{1}{3}\big(\frac{2}{3}\big)^{n-1}+1$$ $$a_n-a_{n-1}=-\frac{1}{2}\big(\frac{2}{3}\big)^n+1$$ $$a_n=a_{n-1}-\frac{1}{2}\big(\frac{2}{3}\big)^n+1$$

One way to find recursive formulas given explicit ones that might work in future problems is to use the following formula: If $$a_n=f(n)$$ then $$a_n-a_{n-1}=f(n)-f(n-1)$$ $$a_n=a_{n-1}+f(n)-f(n-1)$$ and that should do it. You could even take the ratio approach that you mentioned: $$\frac{a_n}{a_{n-1}}=\frac{f(n)}{f(n-1)}$$ $${a_n}=\frac{f(n)a_{n-1}}{f(n-1)}$$ Does this help?

Answer 2

You already know that $$a_n-a_{n-1}=\left(\frac23\right)^n + n-\left(\frac23\right)^{n-1} - (n-1)=-\frac12\left(\frac23\right)^n+1$$ but, as explained about an answer to a previous question of yours, this is not a recursion relation since the RHS still depends on $n$. To remedy this, introduce $$b_n=a_n-a_{n-1}$$ If one can find a recursion formula for $(b_n)$, the exercise will be solved, right? And look, by definition, $$b_n=-\frac12\left(\frac23\right)^n+1$$ hence $$b_{n-1}=-\frac12\left(\frac23\right)^{n-1}+1$$ And $b_n$ is almost $\frac23$ times $b_{n-1}$.

To transform "almost" into "exactly", consider $$c_n=b_n-1$$ then $$c_n=-\frac12\left(\frac23\right)^n$$ and for this sequence, a recursion is easy, which reads $$c_n=\frac23\cdot c_{n-1}$$ Now it remains to come back to $(a_n)$, which is done in two steps, first by noting that $c_n=b_n-1$ hence $$b_n-1=\frac23\cdot (b_{n-1}-1)$$ and then by noting that $b_n=a_n-a_{n-1}$ hence $$a_n-a_{n-1}-1=\frac23\cdot (a_{n-1}-a_{n-2}-1)$$ which after a bit of massaging is equivalent to

$$3a_n-5a_{n-1}+2a_{n-2}=1$$

Of course, the fact that the linear combination one arrives at corresponds to the polynomial $$3x^2-5x+2$$ whose roots are $$x=1\qquad x=\frac23$$ is no coincidence, but explaining that might be best kept for another question...

Answer 3

Presumably they want you to find a recursive formula of a certain form, the most commonly taught form being a linear combination of previous terms. If any form was acceptable then you could just write $a_n = (2/3)^n + n + a_{n - 1} - a_{n - 1}$.

A matrix with the behavior you want is the Jordan matrix $$M^n = \begin{bmatrix} 2/3 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}^n$$

which implies that there is some recursions of the form

$$a_{n + 3} = X~a_{n+2} + Y~a_{n + 1} + Z~a_{n}$$

that satisfies your equation. So solving

$$\begin{cases} a_5 = X a_4 + Y a_3 + Z a_2 \\ a_4 = X a_3 + Y a_2 + Z a_1 \\ a_3 = X a_2 + Y a_1 + Z a_0 \\ \end{cases}$$

with your initial conditions gets a solution. I suggest working it out on your own, after you can hover over below to check your solution:

$$\begin{align} X = 8/3,~Y=-7/3,~Z=2/3 \\ \\ 3~a_{n+3} = 8~a_{n+2} - 7~a_{n+1} + 2~a_{n} \end{align}$$

Answer 4

The "straigth-on" approach is to take some progressive finite differences and then decide on that basis the strategy.

In your case $$ \eqalign{ & a_{\,n} = \left( {{2 \over 3}} \right)^{\,n} + n \cr & \Delta a_{\,n} = a_{\,n + 1} - a_{\,n} = 1 - {1 \over 3}\left( {{2 \over 3}} \right)^{\,n} \cr & \Delta ^2 a_{\,n} = a_{\,n + 2} - 2a_{\,n + 1} + a_{\,n} = {1 \over 9}\left( {{2 \over 3}} \right)^{\,n} \cr} $$

then we can cancel the dependence from $(2/3)^n$ by expressing $ \Delta a_{\,n} $ in terms of $ \Delta^2 a_{\,n} $ $$ a_{\,n + 1} - a_{\,n} = 1 - 3\left( {a_{\,n + 2} - 2a_{\,n + 1} + a_{\,n} } \right) $$

to conclude that $$ 3a_{\,n} - 5a_{\,n - 1} + 2a_{\,n - 2} - 1 = 0\quad \left| \; \right.a_{\,0} = 1,\;a_{\,1} = 5/3 $$

Answer 5

$\displaystyle a_n=\bigg(\frac 23\bigg)^n+n$

Let's have $b_n=a_n-n$, it is immediate that $b_n$ verifies $b_{n+1}=\frac 23 b_n\iff 3b_{n+1}=2b_n$

Now if we set $c_n=3a_{n+1}-2a_n=\underbrace{3b_{n+1}-2b_n}_0+3(n+1)-2(n)=n+3$

We have $c_{n+1}-c_n=1$.

This equation once developed gives :

$3a_{n+2}-2a_{n+1}-3a_{n+1}+2a_n=1\iff 3a_{n+2}-5a_{n+1}+2a_n=1$