1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ i would expect the limit to be $3.$ i will see if my intuition is worth anything. $\endgroup$ – abel May 24 '15 at 15:52
  • $\begingroup$ @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. $\endgroup$ – DanielV May 24 '15 at 18:37
  • $\begingroup$ @DanielV, thanks for the clarification. i had a feeing that $n$ can only cause a linear growth. $\endgroup$ – abel May 24 '15 at 18:58
3
$\begingroup$

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

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

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

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How do you find that form? $\endgroup$ – mathlearner May 24 '15 at 10:45
  • $\begingroup$ 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. $\endgroup$ – J.E.M.S May 24 '15 at 10:48
  • $\begingroup$ It is the discrete version of linear differential equations with constant coefficients. $\endgroup$ – Bernard May 24 '15 at 12:40
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ There is a degenerate case where $a_1 = 1/4$ $\endgroup$ – DanielV May 24 '15 at 11:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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