1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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. $$

$\endgroup$
  • $\begingroup$ Thanks for your reply! Can you explain then why the values no longer match after m and k are equal to 47? $\endgroup$ – bkehs Apr 16 '18 at 16:08
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 16 '18 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.