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?

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
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. $$

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for your reply! Can you explain then why the values no longer match after m and k are equal to 47? $\endgroup$
    – bkahso
    Commented Apr 16, 2018 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
    Commented Apr 16, 2018 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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