For any constant k>1 the function f(n) = 1 + k + k^2 + k^3 + .. + k^n is in Θ(k^n)

29 Views Asked by At

I know what theta means we essentially are proving that

c1 * g(n) <= f(n) <= c2*g(n)

I came across this question while looking for asymptote examples and none of the other examples have this format. The ones I have done so far, are literal functions which are fairly straight forward but this f(n) is basically a summation? I am confused on how to go about this, it's a true and false question. Any help would be appreciated!

1

There are 1 best solutions below

2
On

$1 + k + k^2 + k^3 + \ldots + k^n = \frac{1-k^{n+1}}{1-k}$