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

Question

I am trying to solve the following problem.

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 !

Just a shot in the dark, maybe to give some ideas: $k^2-k+1 = (k-1)^2 + k$ — gt6989b, May 29 '23 at 17:42

score 0 · Accepted Answer · edited May 29 '23 at 19:33

0

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.

edited May 29 '23 at 19:33

durianice

2,624

answered May 29 '23 at 19:27

andimon

33

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

1 Answers1