Question

Show that, if c is a positive real number, then g(n) = 1 + c + c² + · · · + cⁿ is:

(a) Θ(1) if c < 1.

(b) Θ(n) if c = 1.

(c) Θ(cⁿ) if c > 1.

The moral: in big-Θ terms, the sum of a geometric series is simply the first term if the series is strictly decreasing, the last term if the series is strictly increasing, or the number of terms if the series is unchanging.

Short answer

The sum of the series can be calculated by using the following formula:

${\mathrm{s}}_{\mathrm{n}}=\frac{\mathrm{a}({\mathrm{r}}^{\mathrm{n}}-1)}{\mathrm{r}-1}$

Where a is the first term of the GP and r is the common ratio.

Step-by-step solution

Simplifying the Geometric Progression

For the given series,

$\mathrm{a}=1,\mathrm{r}=\mathrm{c}$

Applying the sum of the GP formula, we get:

$$\begin{gathered} s_n=\frac{1\left(c^n-1\right)}{c-1} \\ =\frac{c^n-1}{c-1} \end{gathered}$$

Proving the result for c < 1 using the hit and trial method.

let ,c =0 which is less than 1, and put the value of c in $s_n$, we get:

$$\begin{gathered} s_n=\frac{0^n-1}{0-1} \\ =\frac{0-1}{-1}\because o^n=0 \\ =1 \end{gathered}$$

Therefore, we can say that$\mathrm{g}\left(\mathrm{n}\right)$ is $\Theta \left(1\right)$when$c<1.$

for c = 1,

Use the limits to prove this,

$$\begin{gathered} \underset{\mathrm{c}\to 1}{\lim }\frac{{\mathrm{c}}^{\mathrm{n}}-1}{\mathrm{c}-1} \\ =\mathrm{n}.1^{\mathrm{n}-1}\because \underset{\mathrm{x}\to \mathrm{a}}{\lim }\frac{{\mathrm{x}}^{\mathrm{n}}-{\mathrm{a}}^{\mathrm{n}}}{\mathrm{x}-\mathrm{a}}{\mathrm{na}}^{\mathrm{n}-1} \\ =\mathrm{n}.1 \\ =\mathrm{n} \end{gathered}$$

So,

$$\begin{gathered} s_n=n \\ \odot \left(s_n\right)=\odot \left(n\right) \end{gathered}$$

for c > 1

For any number c > 1, the last term of the series can be used to find the theta notation of the entire series because that term will be largest. So, the last term of the series is $c^n$whose theta notation will be$\Theta \left(c^n\right)$