I need to calculate the following recurrence relation (I know how, below is explanation) using method of summation factors:
$\begin{cases} T(0) = 1 \\ T(n) = 4T(n-1) + 3 \end{cases}$
Brief definition of method of summation factors:
Let there be given recursive formula:
$$a_{n}T_{n} = b_{n}T_{n-1} + c_{n}$$
where:
$$a_{n} \neq 0 \iff n \geq 0$$ $$b_{n} \neq 0 \iff n > 0$$
then the solution $T_{n}$ of the recursive formula is defined as:
$$T_{n} = \frac{1}{S_{n}a_{n}}(S_{1}b_{1}T_{0} + \sum_{k = 1}^{n} S_{k}c_{k})$$
where:
$$S_{n} = \frac{a_{1}a_{2}...a_{n-2}a_{n-1}}{b_{2}b_{3}...b_{n-1}b_{n}} \quad \quad \land \quad \quad S_{1} = 1$$
$\begin{cases} T(0) = 1 \\ T(n) = 4T(n-1) + 3 \end{cases}$
Here $a_{n} = 1, b_{n} = 4, c_{n} = 3$
So $S_{n} = \frac{1^{n-1}}{4^{n-1}} = \frac{1}{4^{n-1}}$
Plugging into formula:
$$T(n) = 4^{n-1} \Bigg( 1*4*1 + \sum_{k=1}^{n} \Big( \frac{1}{4^{k-1}} * 3 \Big) \Bigg)$$
The above calculations are correct and after simplification WolframAlpha yielded correct result. Wolfram code:
4^(n-1) * (4 + sum from k = 1 to n of (3/(4^(k-1)))
WolframAlpha's simplified result is
$$T(n) = 2^{2n+1} - 1$$
which yields: $7, 31, 127, 511, 2047$ for $n = 1, 2, 3, 4, 5$ respectively, which are all correct.
My problem is: I know how to solve such relations using this method (I need to use this method, not my choice).
But what if there was $T(1) = 1$ as a stop condition instead of $T(0) = 1$?
So the relation would be of the form:
$$\begin{cases} T(1) = 1 \\ T(n) = 4T(n-1) + 3 \end{cases}$$
I expect $T(n) = 2^{2n - 1} - 1$ as a closed-form final answer, which yields $1, 7, 31, 127, 511$ for $n \in [1, 5]$
I am just not sure what should I do differently when dealing with the calculations, in order to obtain that result.
Another way:
Let $T(m)=U(m)+a$
$$3=T(n)-4T(n-1)=U(n)-4U(n-1)-3a$$
WLOG set $a=-1,$
$T(m)=U(m)-1,$
$1=T(0)=U(0)-1\implies U(0)=2$
to find $$U(n)=4U(n-1)=4^rU(n-r)=4^nU(0)=2\cdot4^n=2^{1+2n}$$