Here's another one:
A friend of mine (Sam Elder) was trying to calculate the number of combinations on a simplex lock with $n$ buttons. After some work he had gotten a recurrence which I'm going to write as $2A_m = 1+\sum_{k=0}^m \binom{m}{k}A_{k}$, which he showed to me. My thought process went like this:
Hmm, this looks like the recurrence for the Bernoulli numbers. How did we prove the recurrence for the Bernoulli numbers again? One way is to use the well-known fact that $\sum_{n=0}^{\infty} n^m = -\frac{B_{m+1}}{m+1}$, so$-\frac{B_{m+1}}{m+1} = \sum_{n=0}^{\infty} n^m = \sum_{n=0}^{\infty}(n+1)^m = -\sum_{k=0}^m\binom{m}{k}\frac{B_{k+1}}{k+1}$.
Working backwards, what I need to do is find a sequence of functions $f_m(n)$ satisfying $2f_m(n+1) = \sum_{k=0}^m\binom{m}{k}f_{k}(n)$. This leads naturally to the choice $f_m(n) = \frac{n^m}{2^n}$. So the number of simplex combinations on m buttons is
$A_m = \sum_{n=1}^{\infty} \frac{n^m}{2^n}.$
Sam did not find this formula incredibly helpful.
(Continuing the analogy with the Bernoulli numbers, we can also derive the formula$\sum_{n=1}^x \frac{n^m}{2^n} = A^m-\frac{(x+A)^m}{2^x},$where we interpret $A^m$ as $A_m$.)
