I was asked to solve this recurrence:
$F(n) = 2 * F(n - 1) + 2^{n+1}$ ; with $F(0) = 0$
I should solve this recurrence with two appraoches: with the characteristic function and with cascading. I know how both techniquese work, but I could not really solve the equation.
Firstly, with the characteristic function:
I ended up with
$F(n) - 2 * F(n - 1) = 2^{n+1}$ (which would mean $(x - 2) * (x - 2) = 0$)
Since there should be a number $ x^n * n^0$ on the right side and not $ x^{n+1} * n^0$, I do not know how to continue (of course, I know that $ 2^{n+1} = 2 * 2^n$). If I calcuate the root with $2^{n+1}$ or $4^{(n+1)/2}$, I get a wrong closed formular for the recurrence. Could you please tell me how to get something of the form $x^n * n^0$ on the right side of the equation?
Secondly, with cascading:
I ended up with something like $ F(n) = ((((2 * 0 + 2^1) * 2 + 2^2) * 2 + 2^3) * ... ) * 2 + 2^{n+1} $
But how do I conclude a concrete formula (if my approach is correct)?!
I would be really happy if someone could help me.
All the best!
I conjecture that $F(n)=n\cdot 2^{n+1}$ we get that $$n\cdot 2^{n+1}=(n-1)\cdot2^{n+1}+2^{n+1}=n2^{n+1}$$ I got this by computing $F(1)=4$ and $F(2)=16$ and $F(3)=48$ the $48$ was really helpful since it's $3\cdot 16$ and we are computing $F(3)$ to confirm my guess I also computed up to $5$ and we get $F(5)=5\cdot 64$.