Closed form of recurrence with two inputs This question comes from a relatively simple coding challenge at Codesignal, but represents an interesting CS/math puzzle. The question states:
&quot;When a candle finishes burning it leaves a leftover. m leftovers can be combined to make a new candle, which, when burning down, will in turn leave another leftover.
You have c candles in your possession. What's the total number of candles you can burn, assuming that you create new candles as soon as you have enough leftovers?&quot;
So the inputs are the number of starting candles and how many burned candles can be reused recursively to make new candles.
Now, I solved this with a while loop, and the loop itself just involves division and modulo math:
def candles(c, m):
    
    burned=c
    while c&gt;=m:
        burned+=c//m
        c=(c%m)+c//m
    return burned

But many of the other solutions go straight to closed form (which is obviously better in terms of complexity). I tried to figure out how they were reaching this by writing out a recurrence relation, but I can't do it... Here's an example of an accepted solution:
return c + (c - 1) // (m - 1)
I was hoping someone could help me figure out what techniques are used to arrive at this solution.
The candle burning rules are as follows: if you have c&gt;=m candles, you can remove (m-1) of them and score m points while doing so. If you have fewer than c&lt;m candles, then you score c points and are then done.
The total number of points you can score are then the points you score at the end (c % (m-1)), and the number of points you score before then (m * (c // (m-1))).