归纳总和的大O证明

Question

我一直试图解决这个问题:

?(k=0,n)3k = O(3n)

我一直在网上浏览各种各样的东西,但我似乎无法解决它.我知道它涉及Big O的正式定义,其中

|f(x)| <= C*|g(x)|, x>=k

由于它们是相同的,我假设C是我必须通过归纳找到的一些值来证明原始陈述,并且k = 0.

感谢您对此的帮助.

Answer 1

?(k=0,n)3k 
= 30 + 31 + ... + 3n
= (1 - 3n+1) / (1 - 3) ; sum of geometric series
= (3/2)*3n - k
<= c*3n ; for c >= 3/2 
= O(3n)