# Closed-Form Expression for Recursive Function

Let $k \in \mathbb{N}$ and $m \in \mathbb{R}$. Consider the following function $S\colon \mathbb{R} \times \mathbb{N} \to \mathbb{R}$: $$S(m,k) = \begin{cases} 3m & \text{if } k = 0, \\ 4S(\tfrac{m}{2},k-1)+3m & \text{if } k \geq 1. \end{cases}$$ Find a closed-form expression for $S(m,k)$ using repeated substitution.

Prove the correctness of the expression you obtained.

When using repeated substitution, I found the formula $$\sum_{i=0}^{k} 4^i\frac {3m}{2^i},$$

whereas the solution has the formula,

$$6m2^k - 3m.$$

I wrote my sum (as well as the original recurrence relation) in Python, and plugged in values from 0 to a 100 for both $m$ and $k$.

For some reason, the sum gets wrong values starting at $m, k = 47, 47$, and follows a weird pattern after that.

Does anyone have any idea what is going on?

## 1 Answer

The two formulas agree: $$\sum_{i=0}^k 4^i \frac{3m}{2^i} = 3m \sum_{i=0}^k 2^i = 3m(2^{k+1}-1) = 6m2^k - 3m.$$

• Thanks for your reply! Can you explain then why the values no longer match after m and k are equal to 47? Apr 16 '18 at 16:08
• The answer depends on how python implements arithmetic, so is off-topic here. One possibility is that you're exceeding the precision of the floating point numbers used by python, but this is just a guess. Apr 16 '18 at 17:28