Θ обозначение суммы геометрического ряда

Question

У меня вопрос по поводу геометрических рядов. Почему

1 + c + c ² + ... + c ⁿ = Θ (c ⁿ )

когда с> 1? Я понимаю, почему это Θ (n), если c = 1, и это Θ (1), если c <1, но я просто не могу понять, почему это Θ (c <sup>n ), если c> 1.

Спасибо!

Answer 1

Сумма первых n членов геометрического ряда

c ⁰ + c ¹ + ... + c ^n-1

определяется по количеству

(c ⁿ - 1) / (c - 1)

Обратите внимание, что если c> 1, то эта величина сверху ограничена c ⁿ - 1, а снизу - c ^n-1 - 1 / c.Следовательно, это O (c ⁿ ) и Ω (c ⁿ ), поэтому это Θ (c ⁿ ).

Надеждаэто помогает!

Answer 2

Пусть c> 1 и g (c) = 1 + c + c ² + ... + c ⁿ .

Первое, что нужно осознатьявляется то, что для некоторого n мы имеем S (n) = (c ^{n + 1} - 1) / (c - 1), где S (n) - сумма ряда.

Итак, мы имеем это (c ^{n + 1} - c ⁿ ) / (c-1) <= (c <sup>n + 1 - 1) / (c - 1) = S (n), поскольку c ⁿ > = 1.

Итак (c ^{n + 1} - c ⁿ ) / (c-1) = (c ⁿ (c-1)) / (c-1) = c ⁿ <= S (n) </p>

Таким образом, мы имеем, что S (n)> = c ⁿ .

Теперь, когда мы нашли нашу нижнюю границу, давайте посмотрим на верхнюю границу.

Обратите внимание, что S (n) = (c ^{n + 1} - 1) / (c - 1) <= (c <sup>n + 1 ) / (c - 1) = ((c ⁿ ) c) / (c -1).

Чтобы просто немного взглянуть на алгебру, давайте y = c / (c-1) и подставим ее вуравнение выше.

Следовательно, S (n) <= y * c <sup>n , где y - просто некоторая константа, поскольку c есть!Это важное наблюдение, поскольку теперь оно кратно c ⁿ .

Так что теперь мы нашли и нашу верхнюю границу.

Таким образом, мы имеем c ⁿ <= S (n) <= y * c <sup>n .

Следовательно, S (n) = Θ (c ⁿ ), когдас> 1.