# proof that powers of 2 are a superincreasing sequence

We will prove a more general fact. If $x\geq 2$ then the sequence given by $a_{k}=x^{k}$ is a superincreasing sequence.

Notice that $a_{1}=x>1=a_{0}$. Now we proceed by induction. We assume that

 $a_{n}=x^{n}>\sum_{j=0}^{n-1}a_{j}=1+x+x^{2}+x^{3}+\cdots+x^{n-1}$

We need to prove that $a_{n+1}=x^{n+1}>\sum_{j=0}^{n}a_{j}$. But

 $x^{n+1}=x\cdot x^{n}\geq 2x^{n}=x^{n}+x^{n}>x^{n}+(x^{n-1}+x^{n-2}\cdots+x+1)$

so we conclude that

 $a_{n+1}>a_{n}+a_{n-1}+\cdots+a_{1}+a_{0}$

and so the sequence is superincreasing.

Title proof that powers of 2 are a superincreasing sequence ProofThatPowersOf2AreASuperincreasingSequence 2013-03-22 15:03:17 2013-03-22 15:03:17 drini (3) drini (3) 4 drini (3) Proof msc 11B83