How can I prove with induction that $c\cdot 2^n \geq T(n)$

Question

given:
$$T(n)=2\cdot T(n-1) + n \space\space ,(n\geq10)$$ and for $n<10$ exists: $T(n)=1$.

How can I prove by induction about $n$ ($n$ $\in$ $\mathbb{N}$) that exists $c>0$ such then for any $n\geq n_0$ (for some $n_0\in \mathbb{N}$):
$$c\cdot 2^n \geq T(n)$$

Answer 1

$ \text{iff} \: \{n|n < 10, n \in \mathbb{N} \},\: T(n) = 1 $

$ \text{else}, \: T(n) = 2* T(n-1) + n $

Prove that $ \forall n \: \exists c: c*2^{n} \geq T(n) $ :

My approach, we know that $T(9) = 1$ Applying the rule of recursion, $ T(10) = 2 * T(9) + 10 = 2*1 + 10 = 12$

Let's say I wanted to find $T(100)$ : $$ T(100) = 100 + 2(T(99)) = 100 + 2(99 + T(98)) = 100 + 2(99 + 2(98 + T(97))) = 100 + 2(99 + 2(98 + 2(97 + 2(96 + ...+2(11+2(10+2(1)))))))))... $$

And in general, $$T(n) = n + 2((n-1) + 2((n-2) + 2((n-3) + ...2(11+2(10+2(1)))))))))...$$ $$T(n) = (2^0)(n) + (2^1)(n-1) + (2^n)(n-3) + ... + (2^{n-11})(11) + (2^{n-10})(10) + (2^{n-9})(1)$$ Let $ S = (2^0)(n) + (2^1)(n-1) + (2^n)(n-3) + ... + (2^{n-11})(11) + (2^{n-10})(10) $, i.e. $ T(n) = S + 2^{n-9} $

---

$ S = (10)(2^{n-10})) + (11)(2^{n-10})) + ... + (n-2)(2^2) + (n-1)(2^1) + (n)(2^0) $

$ -\frac{1}{2} S = (10)(2^{n-11})) + ... + (n-3)(2^2) + (n-2)(2^1) + (n-1)(2^0) + \frac{n}{2}$

$ S -\frac{1}{2} S = (10)(2^{n-10})) + 2^{n-11} + 2^{n-12} +...+ 2 + 1 - \frac{n}{2}$

$ \frac{1}{2} S = (10)(2^{n-10})) + 2^{n-10} - 1 -\frac{n}{2} $

$ S = (10)(2^{n-9})) + 2^{n-9} - n - 2$

$T(n) = (10)(2^{n-9})) + 2^{n-9} - n - 2 + 2^{n-9} $

$ T(n) = 12(2^{n-9}) - n - 2 $

Let $ c * 2^(n) \geq (12)(2^{n-9}) - n - 2 $

Know all you have to do is show that there exists a value of c all n such that

$ c*2^{n} \geq T(n) $

You can easily find a value that satisfies this equation for $ n \geq 10 $ for example $ c = \frac{3}{128} $ works

And for $ n < 10 $, you can let $ c = \frac{1}{2^n} $ and c will always exist

Answer 2

Hint: Notice that if $T(n) \leq c \cdot 2^n$ then $T(n+1) = 2T(n) + n \leq (c + \frac{n}{2^{n+1}})2^{n+1}$ and then think about the sum $c = T(1) + (\frac{1}{4} + \frac{2}{8} + \frac{3}{16} + \frac{4}{32} + \dots + \frac{n}{2^{n+1}} + \dots) = T(1) + 1 = 2$