# 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 2{x}^{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 |