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.
 A: We can write $f(n)=2f(n-1)+k$ as $$f(n)+k=2(f(n-1)+k)\iff g(n)=2g(n-1)$$
where $g(n)=f(n)+k$ is a geometric progression.
Since we have $g(n)=2^{n}g(0)=2^{n}(f(0)+k)$, we have
$$f(n)=g(n)-k=2^{n}(f(0)+k)-k=2^{n}f(0)+(2^{n}-1)k.$$
A: $$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$
A: 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
$$
A: 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.  
A: Here is a generating function method that usually works (not elegant in this case, though).
First of all, remember the infinite geometric progression formula (we'll use it multiple times):
$$|x|<1\implies 1+x+x^2+x^3+\cdots=\sum_{n=0}x^n=\frac{1}{1-x}$$
Let $G(x)=\sum_{n=0}f(n)x^n$. The coefficient of the $x^n$ term is $f(n)$.
Multiply both sides by $x^n$:
$$f(n)x^n=2f(n-1)x^n+kx^n$$
Now, this equation holds $\forall n\ge 1, n\in\mathbb N$, so we add up all the equations that we can create by letting $n=1, n=2$, etc.
$$\begin{align}
\sum_{n=1}f(n)x^n &=\sum_{n=1}2f(n-1)x^{n}+k\sum_{n=1}x^n 
\\ 
\iff G(x)-f(0) &=2xG(x)+k\left(\frac{1}{1-x}-1\right) 
\\ 
\iff G(x)&=\frac{k}{(1-x)(1-2x)}+\frac{f(0)-k}{1-2x}
\end{align}$$
Let $\left[ G(x) \right]_{x^n}$ denote the coefficient of the $x^n$ term of the power series $G(x)$.
Note that we have the following facts (we'll use them):
$$\begin{align}\left[ \frac{1}{1-ax} \right]_{x^n}&=a^n
\\
\left[ \frac{1}{(1-ax)(1-bx)} \right]_{x^n}&=\sum_{j=0}^{n}a^{j}b^{n-j}\end{align}$$
Thus we have:
$$\begin{align}
\left[ G(x) \right]_{x^n}&=\left[ \frac{k}{(1-x)(1-2x)} \right]_{x^n}+\left[ \frac{f(0)}{1-2x} \right]_{x^n}-\left[ \frac{k}{1-2x} \right]_{x^n} 
\\\\
&=k\sum_{j=0}^{n}1^j2^{n-j}+f(0)\cdot 2^n-2^nk 
\\\\
&=k\cdot (1+2^1+2^2+2^3+\cdots+2^n)+f(0)\cdot 2^n-2^nk 
\\\\
&=k\cdot \frac{2^{n+1}-1}{2-1}+f(0)\cdot 2^n-2^nk 
\\\\
&=2^{n+1}k-k+f(0)\cdot 2^n-2^nk 
\\\\ 
&=2^n(2k-k)+f(0)\cdot 2^n-k 
\\\\ 
&=2^nk+f(0)\cdot 2^n-k
\\\\
&=2^nf(0)+k(2^n-1)
\end{align}$$

I'm adding some other formulas that might help you in the future:
$$\begin{align}\left[ \frac{1}{(1-x)^k}\right]_{x^n}&=\binom{n+k-1}{n}=\left(\binom{k}{n}\right)
\\
\left[(1+x)^k\right]_{x_n}&=\binom{k}{n}\end{align}$$
Here $\left(\binom{k}{n}\right)$ denotes multiset coefficient.

A little note: To show how great this method is (and to give you an exercise to see if you understand the method for some practice), I can say that it can be used to find the closed formula for the $n$'th term of the Fibonacci sequence. The useful form of it is (where $F_0=0$):
$$F_n = \frac{(1 + \sqrt{5})^n - (1 - \sqrt{5})^n}{2^n \sqrt{5}}, \forall n\in\mathbb N_0$$
However, our method at first produces this different form:
$$F_n=\frac{\sum_{j=0}^{n-1}(1+\sqrt{5})^{j}(1-\sqrt{5})^{n-j-1}}{2^{n-1}}, \forall n\in\mathbb N_0$$
Using algebraic manipulations, you can change one to the other. The former formula is more useful because it helps us see the shorter formula that we can have:
$$F_n = \lfloor \frac{(1 + \sqrt{5})^n}{2^n \sqrt{5}} + \frac{1}{2} \rfloor=\lfloor \frac{\phi^n}{\sqrt{5}}+\frac{1}{2} \rfloor, \forall n\in\mathbb N_0$$
This question is about learning how to solve recurrence relations in general, so this may be useful.
