$a_{n+1}=4a_n+n+1$ Find Closed Form

Question

\begin{cases} a_{n+1}=4a_n+n+1\\ a_0=1\\ \end{cases}

a. find $\alpha,\beta$ such that if we plug in $b_n=a_n+\alpha n+\beta$ we will get $b_{n+1}=4b_n$

b. find $b_n$ explicitly

So we first plug in the guess

$a_{n+1}=4a_n+n+1$ but $a_n=b_n-\alpha n-\beta$ so

$a_{n+1}=4(b_n-\alpha n-\beta)+n+1=4b_n+n(1-4\alpha)+1-4\beta$

then we look at $1-4\alpha=0\iff \alpha=\frac{1}{4}$ and $1-4\beta=0\iff \beta=\frac{1}{4}$ (Why do we do it?)

So we got $b_n=a_n+\frac{1}{4} n+\frac{1}{4}$

looking at $n=0$ we get $b_0=0+n*0+\frac{1}{4}$ so $b_0=\frac{1}{4}$

a. how to continue?

b. is there a place I can read about this process? I was just given examples which I try yo learn from, but I try to undersatnd

Answer 1

Not a single answer so far has tried to address your specific question so I'll try to do just that.

So we have set $b_n = a_n + cn + d$ (I've changed the lettering since it's easier to type, but otherwise it's the same!). You made a slight error when finding $c$ and $d$, so I'll do it out for you. $b_{n+1} = a_{n+1} + cn + c + d = 4a_n + n + 1 + cn + c + d$ $ = 4(b_n - cn - d) + n + 1 + cn + c +d = 4b_n +(1-3c)n + (1+c-3d) $

Now you're asked to find $c,d$ such that $b_{n+1}=b_n$, hence $1-4c=0$ and $1+c+d=0$ which gives us that $c= \frac {1}{3}, d = \frac {4}{9}$. What's the point of defining $b_n$ this way? Well because $b_{n+1}=rb_n$ has a simple solution for any real $r$: $b_n = b_0 r^n $ This is actually the definition of exponentiation when the exponent is a natural number (or negative integer, but that's not relevant right now so don't worry if you don't understand). Plug the solution in yourself if you're still not convinced.

So $b_n = b_0 4^n $, and finally $a_n = b_0 4^n -n/3 -4/9$. I'll leave it to you to find the value of $b_0$.

This area is called recurrence relations, or recursive sequences less commonly. As others have said questions like these are phenomenally similar to the theory of ordinary differential equations, so you could study them to get more ideas. Furthermore, for a question like this, with practice you'll get more confident about what substitutions to make to solve the problem. In this case the $4$ in front of $a_n$ was a very strong hint the answer was going to be exponential in some way.

Some of the other solutions do have some nice solutions that are worth looking at; the characteristic equation is a pretty big deal in recurrence relations, as well as ordinary differential equations.

Answer 2

HINT:

$$\begin{align}a_{n}&=4a_{n-1}+n-1+1\\&=4^2a_{n-2}+4^1n+4^1(-2+1)+n-1+1\\&=4^2a_{n-2}+(4^1+4^0)n+[4^1(-2+1)+4^0(-1+1)]\\&=4^3a_{n-3}+(4^2+4^1+4^0)n+[4^2(-3+1)+4^1(-2+1)+4^0(-1+1)]\\&=\cdots\end{align}$$

Answer 3

To solve this linear difference equation we can proceed as in the case of a linear DE.

The solution can be stated as

$$ a_n = h_n + p_n $$

where

$$ h_n =4 h_{n-1}\\ p_n=4p_{n-1} + n $$

The solution for $h_n$ has the structure

$$ h_n = \alpha^n $$

and substituting

$$ \alpha^n = 4\alpha^{n-1}\to \alpha = 4\to h_n = c 4^n $$

now proposing for $p_n$

$$ p_n = c_n4^n $$

after substitution we have

$$ c_n4^n=4c_{n-1}4^{n-1} + n $$

or

$$ c_n = c_{n-1}+\frac{n}{4^n} $$

with solution

$$ c_n = \frac{1}{9} 4^{-n} \left(\left(9 c_1+4\right) 4^n-3 n-4\right) $$

This solution can be obtained after polynomial considerations and is left as an exercise. Note the similarity with

$$ c_n =\sum_{k=0}^n k x^k = x\frac{d}{dx}\left(\sum_{k=0}^n x^k\right) = x\frac{d}{dx}\left(\frac{x^{n+1}-1}{x-1}\right) = \frac{(n (x-1)-1) x^{n+1}+x}{(x-1)^2} $$

and now making $x = \frac 14$ voila!

Finally

$$ a_n = 4^nc_n = \frac{1}{9}\left(\left(9 c_1+4\right) 4^n-3 n-4\right) $$

etc.

Answer 4

Same approach as Cesareo (anaylogy with linear differential equations), but taking into account the particular form of the non-homogeneous part of the recurrence equation.

Observe that the difference $b_n$ of any two solutions $a_n$ and $a'_n$ satisfies $$b_{n+1}=a'_{n+1}-a_{n+1}=(4a'_n +n+1)-(4a_n +n+1)=4(a'_n-a_n)=4b_n,$$ so $(b_n)$ is a geometric sequence with ratio $4$, i.e. $b_n=b_0\, 4^n$.

Conversely, if we have a particular solution of the recurrence equation $a_n$, $a'_n=a_n+b_n$ $=a_n+b_0\,4^n\;$ is another solution of this equation. So all what remains to find is one particular solution.

Now the non-homogeneous part n + 1 has the standard form of a polynomial in $n$. In this case we try to find a particular solution which is another polynomial of the same degree : $a_n=\alpha n+\beta$. Plugging this in the recurrence equation we obtain \begin{align} &\alpha(n+1)+\beta=4(\alpha n+\beta)+n+1\\ \iff &(3\alpha+1)n+3\beta-\alpha+1=0\\ \iff&\begin{cases}3\alpha+1=0,\\3\beta=\alpha-1.\end{cases} \end{align}

Answer 5

Hint: Try $$a_{n+1}=\frac{13\cdot4^n-4-3n}{9}$$ and prove this by induction.

Answer 6

You have \begin{align} a_{n+1}&=4a_{n}+n+1 \\ a_{n+2}&=4a_{n+1}+n+2 \\ a_{n+3}&=4a_{n+2}+n+3 \end{align} Subtracting the first from the second we have and the second from the third \begin{align} a_{n+2}-a_{n+1}&=4a_{n+1}-4a_{n}+1 \\ a_{n+3}-a_{n+2}&=4a_{n+2}-4a_{n+1}+1 \end{align} Subtracting again, $$ a_{n+3}-2a_{n+2}+a_{n+1}=4a_{n+2}-8a_{n+1}+4a_{n} $$ which leads to the linear recurrence $$ a_{n+3}-6a_{n+2}+9a_{n+1}-4a_n=0 $$ The characteristic polynomial is $X^3-6X^2+9X-4=(X-1)^2(X-4)$. Thus the general solution is $$ a_n=\alpha+\beta n+\gamma 4^n $$ Now we know that $a_0=1$, $a_1=5$ and $a_2=22$, so we have the linear system \begin{cases} \alpha+\gamma=1\\ \alpha+\beta+4\gamma=5\\ \alpha+2\beta+16\gamma=22 \end{cases} that easily leads to $$ \alpha=-\frac{4}{9} \qquad \beta=-\frac{3}{9} \qquad \gamma=\frac{13}{9} $$ hence $$ a_n=\frac{-4-3n+13\cdot 4^n}{9} $$

Answer 7

Solution

Consider applying the method of undetermined coefficients, we assume that $$a_{n+1}+p(n+1)+q=4(a_n+pn+q),$$ namely,$$a_{n+1}-4a_n-3pn+p-3q=0.$$ In comparison with the recursion formula $a_{n+1}-4a_n-n-1=0,$ we have $$-3p=-1,~~~p-3q=-1.$$ Thus,$$p=\frac{1}{3},~~~q=\frac{4}{9}.$$ This shows that $$a_{n+1}+\frac{1}{3}(n+1)+\frac{4}{9}=4\left(a_n+\frac{1}{3}n+\frac{4}{9}\right).$$ Therefore, $\{a_n+\dfrac{1}{3}n+\dfrac{4}{9}\}$ is a geometrical sequence. Thus,$$a_n+\frac{1}{3}n+\frac{4}{9}=\left(a_0+\frac{1}{3}\cdot 0+\frac{4}{9}\right)\cdot 4^n=\frac{13}{9}\cdot 4^n.$$ As a result,$$a_n=\frac{13}{9}\cdot 4^n-\frac{1}{3}n-\frac{4}{9}.$$