Recurrence Relations Closed Form

Question

So, the question is to derive the closed form solution to the recurrence relation $$T(n) = 3T(n-1) + 5,\hspace{5mm} T(0) = 0.$$

$\begin{align}T(n) &= 3T(n-1)+5 \\&= 3(3T(n-2)+5)+5 \\&= 3(3(3T(n-3)+5)+5)+5\end{align}$

I'm just struggling to go from here. I understand that it's $3$ to the power of something but I'm lost on what I have to do after this.

Answer 1

There are two types of solutions here: the homogeneous and the particular. Rewrite the equation as

$$T_n - 3 T_{n-1} = 5$$

The homogeneous solution is simply the solution assuming the RHS is zero. Thus $T_n^{(H)} = A \cdot 3^n$. The particular solution is a simple solution that satisfies the equation and boundary conditions. In this case, $T_n^{(P)} = B$, a constant:

$$B - 3 B = 5 \implies B=-\frac{5}{2} $$

The solution is the sum of the homogeneous and particular solutions:

$$T_n = A \cdot 3^n - \frac{5}{2} $$

$$T(0)=0 \implies A=\frac{5}{2} $$

Answer 2

Calculating the first few values: $0,5,20,65,200$ , dividing by $5$ this is $0,1,4,13,40$ , multiplying by $2$ we get $0,2,8,26,80$ adding $1$ we get $1,3,9,27,81$. Otherwise you can use generating functions:

Let $A=\sum\limits_{n=0}^\infty t(n)x^n$.

Then $A=3xA+5\sum\limits_{n=1}^\infty x^n$ (since $f(0)=0$).

Then $(1-3x)A=\frac{5}{1-x}-5$ so $A=\frac{5}{(1-3x)(1-x)}-\frac{5}{1-3x}=\frac{5}{2(x-1)}-\frac{15}{2(3x-1)}+\frac{5}{3x-1}=\frac{5}{2(x-1)}-\frac{5}{2(3x-1)}=\frac{1}{2}(\sum\limits_{n=0}^\infty 5\cdot 3^{n} -5)$

therefore $f(n)=\frac{5(3^{n}-1)}{2}$

Answer 3

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack} \newcommand{\dd}{{\rm d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\dsc}[1]{\displaystyle{\color{red}{#1}}} \newcommand{\expo}[1]{\,{\rm e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{{\rm i}} \newcommand{\imp}{\Longrightarrow} \newcommand{\Li}[1]{\,{\rm Li}_{#1}} \newcommand{\pars}[1]{\left(\, #1 \,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,} \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$ "$\,$If$\,$" there is a solution which is $n$-independent it should be $\ds{\frac{5}{1 - 3} =-\,\frac{5}{2}}$. It means that $\ds{\,{\rm T}\pars{n} - \pars{-\,\frac{5}{2}}}$ satisfies a homogeneous recurrence equation: \begin{align} \,{\rm T}\pars{n} + \frac{5}{2}=3\bracks{\,{\rm T}\pars{n - 1} + \frac{5}{2}} \end{align} Then, \begin{align} \,{\rm T}\pars{n} + \frac{5}{2}=3^{1}\bracks{\,{\rm T}\pars{n - 1} + \frac{5}{2}} =3^{2}\bracks{\,{\rm T}\pars{n - 2} + \frac{5}{2}}=\cdots= 3^{n}\bracks{\overbrace{\,{\rm T}\pars{0}}^{\ds{=\ \dsc{0}}} + \frac{5}{2}} =\frac{5}{2}\,3^{n} \end{align} which leads to: $$ \color{#66f}{\large\,{\rm T}\pars{n}} =\color{#66f}{\large\frac{5}{2}\pars{3^{n} - 1}} $$