Closed-form expression of a recursive function

Let’s suppose, for the funs, that you go to the store and suddenly the manager tells you “For every 2 pieces of milk, you get 1 bonus.”

So you stop and think.
For 2 pieces, you end up having 3.
For 4 pieces, you end up having 2 as a bonus, and another one from that bonus 2 makes 4 + 2 + 1 = 7.
For 8 pieces, you end up having 4 as a bonus, and 2 from the bonus 4 and additional 1 from the bonus 2 makes 8 + 4 + 2 + 1 = 15.
You say, a great deal!

Note here that we don’t discuss the case where you don’t get bonus from the bonuses as that’s not hard to calculate.

Now let’s abstract “For every k pieces, you get 1 bonus” and we can start working our way to a closed-form expression.

This was my first attempt to solve it using recursion:

function calc(n, k) {
    if (n < k) {
        return n;
    }
    return n + calc(n / k, k);
}

Cool, let’s give that a try:

> calc(2, 2)
3
> calc(4, 2)
7
> calc(6, 2)
10.5

Seems to be working as expected.

In understanding what that does, let’s try to expand the first few terms manually.
n + (n/k) + (n/k)/k + ((n/k)/k)/k + … = n + n/k + n/k^2 + n/k^3 + … = s
This will proceed until one of the terms is less than k.
Then I went ahead and created a function that calculates the summation (using n/k as upper bound, which seems to be good enough):

/* This function represents the following summation
n/k
Σ n/k^i
i=0

*/
function calc2(n, k) {
    var sum = 0;
    var i;

    for (i = 0; i < n / k; i++) {
        sum += n / Math.pow(k, i);
    }

    return sum;
}

The next thing I did was run a delta check on various ranges to calculate abs(calc – calc2). It was 0.00015 after a few iterations, so seems good.
Now if we multiply s by (k – 1) we get s(k – 1) = nk – n + n – (n/k) + (n/k) + … which follows that s = nk/(k – 1). Note that I used infinity as the upper bound, as in the long run this wouldn’t matter much. It might be a little off for the first values, but eventually it should converge.

function calc3(n, k) {
    return n * k / (k - 1);
}

One thing to note is that the lesser k, the better. Otherwise, the limit as k -> Infinity is equal to just n.
If we now instantiate k to 2, we get n * 2, which means that you pay the milk at 50% discount (in the long run), which is a really good thing!