Solving Recurrence Relation with backwards substitution

Question

I am calculating the effiency class of this

R(n) = 2R(n−1)+2.

with the base case of R(1) = 1

using backwards substitution.

My equations came out to

4R(n-2) + 6

8R(n-3) + 14

16R(n-4) +30

I don't see how i can get an equation from this... Is it incorrect?

Answer 1

HINT:

Let $R(m)=T(m)+b$

$\implies T(n)+b=2\{T(n-1)+b\}+2=2T(n-1)+2b+2$

Set $2b+2=b$

Answer 2

When you’re unwrapping a recurrence this way, it’s usually a bad idea to simplify by actually doing the arithmetic. Instead you should have

$$\begin{align*} R(n)&=2R(n-1)+2\tag{*}\\ &=2\big(2R(n-2)+2\big)+2\\ &=2^2R(n-2)+2^2+2\tag{*}\\ &=2^2\big(2R(n-3)+2\big)+2^2+2\\ &=2^3R(n-3)+2^3+2^2+2\tag{*}\\ &=2^3\big(2R(n-4)+2\big)+2^3+2^2+2\\ &=2^4R(n-4)+2^4+2^3+2^2+2\tag{*}\;. \end{align*}$$

At this point the starred lines should suggest the conjecture that

$$R(n)=2^kR(n-k)+2^k+2^{k-1}+\ldots+2^2+2=2^kR(n-k)+\sum_{i=1}^k2^i\tag{1}$$

for $k=0,\ldots,n-1$. If this is true, then for $k=n-1$ we’ll have

$$R(n)=2^{n-1}R(1)+\sum_{i=1}^{n-1}2^i=2^{n-1}+\sum_{i=1}^{n-1}2^i\;,$$

which you should be able to express in closed form. Once you have that closed form, you should prove by induction that it’s correct, since it was based on the conjecture $(1)$, which could conceivably be wrong.