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.

$$f(n) = 2f(n-1) + k \\ f(n-1) = 2f(n-2) + k \\ f(n-2) = 2f(n-3) + k \\ \dots \\ f(1) = 2f(0) + k$$
$$$$
$$\Rightarrow f(n) = 2f(n-1) + k= \\ 2(2f(n-2) + k)+k= \\ 2^2f(n-2)+(2+1)k=2^2(2f(n-3) + k)+(2+1)k= \\ 2^3f(n-3)+(2^2+2+1)k=  \\ \dots \overset{*}{=} \\ 2^nf(0)+(2^{n-1}+2^{n-2}+\dots +2+1)k$$
Therefore, $$f(n)=2^nf(0)+k\sum_{i=0}^{n-1}2^i= \\ 2^nf(0)+k\frac{2^n-1}{2-1}= 2^nf(0)+(2^n-1)k$$
EDIT:
$(*):$ We see that $2^3f(n-3)+(2^2+2+1)k$ is of the form $2^jf(n-j)+(2^{j-1}+2^{j-2}+\dots+2^2+2+1)k$
After some steps we have the following:
$2^nf(n-n)+(2^{n-1}+2^{n-2}+\dots+2^2+2+1)k= \\ 2^nf(0)+(2^{n-1}+2^{n-2}+\dots+2^2+2+1)k$
