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.

I'm not 100% sure I got what you mean, but for this sort of problems (arbitrary constants $s, t$) a difference equation is a good approach, as you immediately get rid of $t$:
$$
a_k = s a_{k-1} + t\\
a_{k+1} = s a_k + t
$$
now define $\Delta a_{k+1} = a_{k+1} - a_k$. You get 
$$
\Delta a_{k+1} = s \Delta a_k  = s^2 \Delta a_{k-2} =\ldots s^{k-1}\Delta a_1
$$
Now sum over $k$ to 'difference back', do some algebra and you get your result.  
