Matlab questions about $a_{n+1} = 4a_{n} + n +1$

Question

Solve the equation with Matlab

Given: $a_{n+1} = 4a_{n} + n +1$
Start condition: $a_{i}=0$

Questions:

a) Find x,y for: $b_{n} = a_{n}+xn+y$
such that: $b_{n+1}=4b_{n}$

b) Find an explicit formula for $b_{n}$

c) Write recursive function with input n

I'll be very grateful for your help!

Answer 1

Hint

So, it's a hint about the general term of the $a_n$. Hopefully, you can solve the rest.

We can't use the general solution for the homogeneous relation, but we can reduce our relation to the homogeneous case with some manipulations. Namely \begin{align} a_{n+1} &= 4a_n + n + 1 \tag 1 \\ a_{n+2} &= 4a_{n+1} + n + 1 + 1 \tag 2 \end{align} Now, if you subtract $(1)$ from $(2)$, you get rid of $n$ term, but increase order of the recurrence relation. \begin{align} a_{n+2} - a_{n+1} = 4 a_{n+1} - 4a_n + 1 \implies a_{n+2} = 5a_{n+1} - 4a_n + 1 \end{align} Again, do homogenization procedure as before \begin{align} a_{n+2} &= 5a_{n+1} - 4a_n + 1 \tag 3 \\ a_{n+3} &= 5a_{n+2} - 4a_{n+1} + 1 \tag 4 \end{align} Subtract $(3)$ from $(4)$ to get rid of free term, but again you increase the order of the recurrence. \begin{align} a_{n+3} - a_{n+2} = 5a_{n+2} - 5a_{n+1} - 4a_{n+1} + 4a_n \implies a_{n+3} - 6a_{n+2} + 9a_{n+1} - 4a_n = 0 \tag 5 \end{align} Now, $(5)$ is homogeneous recurrence relation of $3^{\text{rd}}$ order. As usual, you assume the solution of the form $a_n = r^n$, to get relation's characteristic polynomial $$ r^3 - 6r^2 + 9r - 4 = 0 \tag 6 $$ It's a cubic equation, and generally you can get some messy roots, even complex sometimes, but for this particular equation $(6)$ roots are simple. Namely, you start from guessing, since coefficients are integer. Simplest guess $r= 1$ turns out to be root. I leave performing polynomial long division procedure to you to get $$ r^3 - 6r^2 + 9r - 4 = (r - 1)(r^2 - 5r + 4) $$ Which can be further reduced to $$ r^3 - 6r^2 + 9r - 4 = (r - 1)^2 (r - 4) $$ and roots are $r_{1, 2} = 1,\ r_3 = 4$.

So, general solution is $a_n = A\ r_{1,2}^n + Bn\ r_{1,2}^n + C\ r_3^n = A + Bn + C4^n$

As you may see, you have $3$ different coefficients to deal with, and only one initial condition. This happened because we artificially increased the order of our relation. Just substitute this solution to the given recurrence relation to get rid of extra coefficients. \begin{align} a_{n+1} & = A + B(n+1) + C4^{n+1} &= A + B + Bn + C4^{n+1} \\ a_{n+1} &= 4a_n + n + 1 = 4A + 4Bn + C4^{n+1} + n + 1 &= 4A + 1 + (4B+1)n + C4^{n+1} \end{align} which leads to the linear system \begin{align} 4A + 1 &= A + B \\ 4B + 1 &= B \end{align} It has a solution $A = -\frac 49$ and $B = -\frac 13$, so $$ a_n = -\frac 49 - \frac 13n + C 4^n $$ Now, you can use initial condition $a_1 = 0$ $$ a_1 = -\frac 49 - \frac 13 + 4C = 0 \implies 4C = \frac 79 \implies C = \frac 7{36} $$ So finally $$ a_n = -\frac 49 - \frac 13n + \frac 7{36}4^n $$

Update

I just realized that your questions hiddenly lead to shorter answer. So, for the $(a)$ part, let's find $b_n$. \begin{align} b_{n+1} &= a_{n+1} + x(n+1) + y = 4b_n \tag 7\\ b_n &= a_n + xn + y \tag 8 \end{align} Now, you use recurrence relation for the $a_{n+1}$ and equate $(7)$ and $(8)$. $$ 4a_n + n + 1 + xn + x + y = 4a_n + 4xn + 4y \implies (x+1)n + x + y + 1 = 4xn + 4y $$ That leads to the system \begin{align} x + 1 &= 4x \\ x + y + 1 &= 4y \end{align} and solutions are $x = \frac 13$ and $y = \frac 49$. So $$ b_n = a_n + \frac 13n + \frac 49 $$ You can find initial condition now $$ b_1 = a_1 + \frac 13+ \frac 49 = \frac 79 $$ You have two options now. First, realize that $b_{n+1} = 4b_n$ is a geometric progression and simply use general term equation for that $$ b_n = b_1 4^{n-1} = \frac 79 4^{n-1} = \frac 7{36} 4^n, $$ or imagine you don't know that and use same technique we've already applied. Characteristic equation of the relation $b_{n+1} = 4b_n$ is $$ r = 4 $$ so general solution would be $b_n = C4^n$. Now substitute initial condition $$ b_1 = \frac 79 \implies \frac 79 = 4C \implies C = \frac 7{36} \implies b_n = \frac 7{36}4^n $$

Than concludes question $(b)$. By the way, now you can easily find the general term for the $a_n$. $$ a_n = b_n - \frac 13n - \frac 49 = \frac 7{36}4^n - \frac 13 n - \frac 49 $$ which of course, is the same answer we obtained before. If you're wondering why I even bothered solving this problem using general procedure, it's because normally we don't know hints and clues like $(7)$ and $(8)$, but if you use general procedure, you can always approach to the solution one way or another.

Another Update

For the $(c)$ I'm assuming you need to write a recursive function for the $a_n$. It is pretty straightforward. Just program recurrence relation directly $$ a_{n+1} = 4a_n + n + 1 $$ There's one trick though. You need to write a function that takes an argument, not a relation on the argument, like $n+1$. So, slightly rewrite the relation as $$ a_n = 4a_{n-1} + (n-1) + 1 = 4a_{n-1} + n $$ and also keep in mind that $a_1 = 0$. So code would be

function retval = an(n)
if n == 1
    retval = 0;
else
    retval = 4*an(n-1) + n;
end