# Find the limit of the sequences: $a_{n+1}=3a_n - n + 1$ and $(a_n)^\frac{1}{n}$ with $a_0 > 0$

Let $a_0 > 0$ and $$a_{n+1}=3a_n - n + 1.$$

I have to find its limit. I have also to find the limit of $(a_n)^\frac{1}{n}$. But this seems even more complicated. For the first part I've used the comparison $$a_n>\frac{n-1}{2}$$ and I've got that the limit is $\infty$.But I've no clue about the second limit.

• i would expect the limit to be $3.$ i will see if my intuition is worth anything. – abel May 24 '15 at 15:52
• @abel Since the general form of $a_{n+1} = A~a_n + B~n + C$ is $$a_{n+1} = \frac{A^n - 1}{(A - 1)^2}\bigg(AB + AC - C\bigg) - \frac{nb}{A - 1} + a_1~A^n$$ so if your intuition was based on $A = 3$, then it is correct. – DanielV May 24 '15 at 18:37
• @DanielV, thanks for the clarification. i had a feeing that $n$ can only cause a linear growth. – abel May 24 '15 at 18:58

$$a_{n+1} = 3a_n - n + 1 \tag{A}$$ $$a_{n+2} = 3a_{n + 1} - (n + 1) + 1\tag{B}$$

So

$$a_{n+2} = 4a_{n+1} - 3a_n - 1 \tag{B minus A}$$

Matrix form:

\begin{align} \begin{bmatrix} a_{n+2} \\ a_{n+1} \\ 1 \end{bmatrix} &= \begin{bmatrix} 4 & -3 & -1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} a_{n+1} \\ a_{n} \\ 1 \end{bmatrix} \\ % &= \begin{bmatrix} 4 & -3 & -1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}^n \begin{bmatrix} a_{2} \\ a_{1} \\ 1 \end{bmatrix} \end{align}

Jordan decomp:

\begin{align} \begin{bmatrix} a_{n+2} \\ a_{n+1} \\ 1 \end{bmatrix} &= \left( \underbrace{\begin{bmatrix} 1 & 1 & 1 \\ \frac 13 & 1 & 0 \\ 0 & 0 & 2 \end{bmatrix}}_P \underbrace{\begin{bmatrix} 3 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}}_D \underbrace{\begin{bmatrix} \frac 32 & -\frac 32 & -\frac 34 \\ -\frac 12 & \frac 32 & \frac 14 \\ 0 & 0 & \frac 12 \end{bmatrix}}_{P^{-1}} \right)^n \begin{bmatrix} a_{2} \\ a_{1} \\ 1 \end{bmatrix} \\ &= \begin{bmatrix} 1 & 1 & 1 \\ \frac 13 & 1 & 0 \\ 0 & 0 & 2 \end{bmatrix} \begin{bmatrix} 3 & 0 & 0 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}^n \begin{bmatrix} \frac 32 & -\frac 32 & -\frac 34 \\ -\frac 12 & \frac 32 & \frac 14 \\ 0 & 0 & \frac 12 \end{bmatrix} \begin{bmatrix} a_{2} \\ a_{1} \\ 1 \end{bmatrix} \\ &= \begin{bmatrix} 1 & 1 & 1 \\ \frac 13 & 1 & 0 \\ 0 & 0 & 2 \end{bmatrix} \begin{bmatrix} 3^n & 0 & 0 \\ 0 & 1 & n \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \frac 32 & -\frac 32 & -\frac 34 \\ -\frac 12 & \frac 32 & \frac 14 \\ 0 & 0 & \frac 12 \end{bmatrix} \begin{bmatrix} a_{2} \\ a_{1} \\ 1 \end{bmatrix} \\ &= \begin{bmatrix} 1 & 1 & 1 \\ \frac 13 & 1 & 0 \\ 0 & 0 & 2 \end{bmatrix} \begin{bmatrix} 3^n & 0 & 0 \\ 0 & 1 & n \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} \frac 32 & -\frac 32 & -\frac 34 \\ -\frac 12 & \frac 32 & \frac 14 \\ 0 & 0 & \frac 12 \end{bmatrix} \begin{bmatrix} 3a_{1} + 1 \\ a_{1} \\ 1 \end{bmatrix} \\ &= \frac{1}{4}\begin{bmatrix} (12a_1 + 3)~3^n + 2n + 1 \\ (4a_1 + 1)~3^n + 2n - 1 \\ 1 \end{bmatrix} \end{align}

So

$$a_{n+1} = \frac{1}{4} \bigg( (4a_1 - 1)~3^n + 2n + 1 \bigg)$$ or $$a_{n} = \frac{1}{12} \bigg( (4a_1 - 1)~3^n + 6n - 3 \bigg)$$

So it is clear that

$$\lim_{n \to \infty} a_{n} \to \infty$$

and

$$\lim_{n \to \infty} \sqrt[n]{a_{n}} = \begin{cases} \\ 4a_1 - 1 = 0 &\quad& 1 \\ \\ 4a_1 - 1 \ne 0 &\quad& 3 \\ \\ \end{cases}$$

• The first limit is wrong. It should be $\lim_{n\to\infty}\sqrt[n]{a_n}=1$ if $4a_1-1=0$. – xpaul May 24 '15 at 14:16
• Ah thanks, I'll correct that. – DanielV May 24 '15 at 15:40

You can use this way to do. Note $$a_{n+1}=3a_n - n + 1, a_n=3a_{n-1}-n+2$$ and hence $$a_{n+1}-a_n=3(a_n-a_{n-1})-1.$$ or $$a_{n+1}-a_n-\frac12=3(a_n-a_{n-1}-\frac12).$$ So $a_{n}-a_{n-1}-\frac12=3^{n-1}(a_1-a_0-\frac12)$ or $a_{n}-a_{n-1}=\frac12+3^{n-1}(a_1-a_0-\frac12)$ and hence \begin{eqnarray} a_n&=&a_0+(a_1-a_0)+(a_2-a_1)+\cdots+(a_n-a_{n-1})\\ &=&a_0+\sum_{k=1}^n[\frac{1}{2}+3^{k-1}(a_1-a_0-\frac12)]\\ &=&a_0+\frac{1}{4}[(3^n-1)(4a_0+1)+2n]. \end{eqnarray} Thus $\lim_{n\to\infty}a_n^{1/n}=1$ if $4a_0+1=0$ and otherwise $\lim_{n\to\infty}a_n^{1/n}=3.$

You can find exactely what the solution to that reccurence is ($A\cdot3^n+\frac{1}{2}n-\frac{1}{4}$) and than just calculate the limit.

• How do you find that form? – mathlearner May 24 '15 at 10:45
• It is a general approache to linear reccurences first solve linear part $a_{n+1}=3a_n$ than find any solution to $a_{n+1}=3a_n-n+1$ (if nonhomogenius part is polynomial we search polynomial) and general solution is sum of that two solutions. – J.E.M.S May 24 '15 at 10:48
• It is the discrete version of linear differential equations with constant coefficients. – Bernard May 24 '15 at 12:40

Let's prove by induction that $$a_n=3^na_0+b_n$$ where $n\le b_n\le3^{n-1}\quad(*)$.

This is certainly true for $a_0$. And $$a_{n+1}=3a_n-n+1=3(3^na_0+b_n)-n+1=3^{n+1}a_0+3b_n-n+1$$ so let $$b_{n+1}=3b_n-n+1$$ From $(*)$, $$n+1\le 3n-n+1\le b_{n+1}\le3^{n}-n+1\le 3^n$$ which proves our assertion.

Now, $$\lim_{n\to\infty}\sqrt[n]{3^n+n}\le\lim_{n\to\infty} \sqrt[n]{a_n}\le\lim_{n\to\infty}\sqrt[n]{3^n+3^{n-1}}$$

Thus, the limit is $3$.

• There is a degenerate case where $a_1 = 1/4$ – DanielV May 24 '15 at 11:55