How to deduce a closed formula given an equivalent recursive one? I know how to prove that a closed formula is equivalent to a recursive one with induction, but what about ways of deducing the closed form initially?
For example:
$$ f(n) = 2 f(n-1) + 1 $$
I know how to use induction to prove that $\forall n \ge1$:
$$ f(n) = 2^n f(0) + 2^n - 1 $$
And I was able to come up with that formula in the first place just by examining it informally.  It seems like there should have been a straightforward, formal way to deduce the closed form from the recursive definition in the first place, but I'm blanking.
I know it's not always easy (e.g. Fibonacci) but it seems like it ought to be here.  For example, how might I go about procedurally deducing the closed form for:
$$ f(n) = 2*f(n-1) + k $$
Thanks.

When I see something like that, I consider multiplying both sides by $2^{-n}$:
$$
\overbrace{2^{-n}f(n)}^{g(n)}=\overbrace{2^{1-n}f(n-1)}^{g(n-1)}+2^{-n}k
$$
Then, since $g(n)=g(n-1)+a_n\implies g(n)=g(0)+\sum\limits_{j=1}^na_j\,$, we have
$$
\begin{align}
\overbrace{2^{-n}f(n)}^{g(n)}
&=\overbrace{f(0)}^{g(0)}+\sum_{j=1}^n2^{-j}k\\
&=f(0)+\left(1-2^{-n}\right)k
\end{align}
$$
Thus, multiplying both sides by $2^n$ yields
$$
f(n)=2^nf(0)+\left(2^n-1\right)k
$$
