$e(k(k−1)+1)<2^{(k−1)} \quad \forall k \geq 9$.

Question

I am trying to solve the following problem.

$e(k(k−1)+1)<2^{(k−1)} \quad \forall k \geq 9$.

What have I tried so far:

I tried proving this problem by induction on k.

(Base Case) For k=9, we have that 198.43...<256. So Base Case holds.

I am stuck on the inductive step.

Assuming the Inductive Hypothesis that

$e(k(k-1)+1)<2^{k-1}$

I tried to show that $e((k+1)(k)+1)<2^{k}$ by expanding the brackets $e(k^2-k+1)$ and then re-arraning the terms to make use of the inductive hypothesis. I got stuck at this point.

Any help on how to tackle such problems would be greatly appreciated !

Answer 1

Solution: Base case holds as shown in the question.

Since $2k<k(k-1)+1$ and by inductive hypothesis: $e((k+1)(k)+1)=e(k^2+k+1)=e(k^2-k+1+2k)=e(k(k-1)+1)+e(2k)<2^{k-1}+e(k(k-1)+1)<2^{k} \; \square$

Solution just popped randomly in my mind. Hope it is valid :D.