proof that powers of 2 are a superincreasing sequence

We will prove a more general fact. If $x\ge 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+\mathrm{\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\ge 2x^n=x^n+x^n>x^n+(x^{n-1}+x^{n-2}\mathrm{\cdots }+x+1)$$

so we conclude that

$$a_{n+1}>a_n+a_{n-1}+\mathrm{\cdots }+a_1+a_0$$

and so the sequence is superincreasing.

Title	proof that powers of 2 are a superincreasing sequence
Canonical name	ProofThatPowersOf2AreASuperincreasingSequence
Date of creation	2013-03-22 15:03:17
Last modified on	2013-03-22 15:03:17
Owner	drini (3)
Last modified by	drini (3)
Numerical id	4
Author	drini (3)
Entry type	Proof
Classification	msc 11B83