Recurrence: Theta of t(n) = 4t(n-1) -15

Question

First let me start off by saying that I am using the substitution method to solve this equation.Although any other methods will be welcomed, this is just the particular method I feel comfortable with.

I am getting to the end of the problem, but I have been unable to progress because I am stuck.

The problem is finding theta of

$$ t(n) = 4t(n-1) - 15 $$

Using the substitution method I was able to come up with...

$$ 4^2t(n-2)-2(15) $$

$$ 4^3t(n-3)-3(15) $$

$$ 4^k t(n+1-k)-k(15) $$

Then I tried to show this in summation form,

$$\sum_{i=n+1-k}^n i$$

I am fine with the problem up until the summation point, I am not sure what to do after summation in order to fully prove an answer.

Any help or guidance is appreciated it.

Answer 1

Well, given that $$t(n)=4t(n-1)-15;\qquad t(0)=t_0$$ We will, by inspection, guess that a solution might look like $$t(n)=4^nt_0-15\sum_{k=0}^{n-1}4^k\qquad (1)$$ This can be proven using induction. Assume that $(1)$ holds for some $n$. Consider $$t(n+1)=4t(n)-15$$ Using the inductive hypothesis we have $$t(n+1)=4[4^nt_0-15\sum_{k=0}^{n-1}4^k]-15$$ $$=4^{n+1}t_0-15\sum_{k=0}^{n-1}4^{k+1}-15$$ $$=4^{n+1}t_0-15\left(\sum_{k=1}^{n}4^n+1\right)=4^{n+1}t_0-15\sum_{k=0}^{n}4^k$$ Which is of the form $(1)$, thus it suffices to say that because $t(1)$ is of the form $(1)$, all $t(n)$ are of the form $(1)$. Now finally we are able to simplify $(1)$ using the partial sum formula for a geometric series and get $$t(n)=4^nt_0-15\frac{1-4^n}{1-4}=4^nt_0+5(1-4^n)$$ $$=4^n(t_0-5)+5$$

Note I got a guess for what the answer would be by computing $$t(1)=4t_0-15$$ $$t(2)=4^2t_0-4\cdot 15-15$$ $$t(3)=4^3t_0-4^215-4\cdot 15-15$$ And so on, and then looked at the patterns, similar to you but going up not down.

Answer 2

We know from theory that a nonhomogeneous linear recurrence will be in the form of a general solution plus a particular solution.

The general solution will come from solving the related homogeneous linear recurrence.

$h(n)=4(h(n-1))$

Looking at the characteristic polynomial $x-4=0$, we know this will then be of the form $h(n)=c_1 4^n$ for some constant $c_1$

The particular solution will be of a similar form as the nonhomogeneous part of the linear recurrence (with possible shifts due to possible overlap with general solution). The nonhomogeneous part in this case is $-15$, so the expected particular solution will be a polynomial of degree zero, i.e. a constant. Let this constant be called $p(n)=d_1$. Plugging the particular solution into the recurrence will allow you to solve for the specific constants.

$p(n)=4(p(n-1))-15\Rightarrow d_1=4d_1-15\Rightarrow d_1=5$

Now that we have the particular solution, and knowing the general form of the homogeneous part, we know the closed form solution will look like the following:

$$t(n)=h(n)+p(n)=c_14^n + 5$$

Given initial conditions, one can now solve for $c_1$. Let $t(0)=t_0$ be our initial condition. Then we have:

$$t_0=t(0)=c_14^0+5$$, implying that $c_1=t_0-5$

The closed form solution is then:

$$t(n)=(t_0-5)4^n+5$$