Re: closed form for T(n) = c^n + T(n-1)

In <Pine.NEB.4.62.0602110858330.26237@xxxxxxxxxxxxxxxx> Daniel Cer <cer@xxxxxxxxxxxxxxxx> writes:

T(0) = a
T(n) = c^n + T(n-1)

Of course, when c is 2, T(n) = (a)*2^n. But, is there a general closed form
for arbitrary c, or at least for when c is an arbitrary positive integer?

Sorry, I just noticed a cognitive misfire in my original post. When c is
2, the closed form is: T(n) = a*2^(n+1) - a

-Dan

That doesn't seem right. I make it T(n) = 2^(n+1) - 2 + a for c = 2,
and T(n) = (c^(n+1)-1)/(c-1) - 1 + a in general

Perhaps you meant the recurrence relation to be T(n) = a*c^n + T(n-1) ?
In that case it's T(n) = a*(c^(n+1)-1)/(c-1)
which gives T(n) = a*(2^(n+1)-1) (same as your latest) for c = 2

HTH,
David
.