Recursion equation

Question

$$f_k = \sum\limits_{k = 1}^{k-1} (f_i + f_{k - i}), \text{ when } k \ge 2, \text{ and } f_1 = 1$$

Find/guess a closed form for $f_k$, i.e. a formula in only the variable $k$; and prove the correctness of your formula by induction.

Another question from the textbook without an answer or any hint. And suggestions ? If you solve and explain it would be awesome. Thanks!

Answer 1

HINT: It never hurts to gather a bit of data, especially when it’s suggested that you might be able to guess a closed form.

$$\begin{array}{rcc} k:&1&2&3&4&5&6\\ f_k:&1&2&6&18&54&162 \end{array}$$

There’s a small glitch in the pattern at the very beginning, but the relationship between $f_k$ and $f_{k+1}$ for $k\ge 2$ sticks out like a sore thumb. If you can’t find a simple relationship, look at the spoiler-protected block below.

If you don’t see it right away, look at $\dfrac{f_{k+1}}{f_k}$ for $k\ge 2$. Alternatively, look at $\frac12f_k$ for $k\ge 2$.

Once you have that relationship, you should be able to conjecture a nice closed form for $f_k$ for all $k\ge 2$, after which proving it by induction is fairly straightforward.