1

So I learnt induction just last week and now practicing, and I have run across a question that has stumped me.

Prove that ($2$ is really small, sorry for improper formatting) $H_{2^k}\geq k+1$; I had started with basis step where for $k=1$ was true, $k=2$ was not, and so forth.

How am I suppose suppose to prove something with induction that is not true?

@Brian M. It is your first guess, sorry but for some reason I am not allowed to comment.

user7349
  • 143
  • 1
  • 1
  • 5

1 Answers1

0

You can't prove something that is not true, with or without induction (barring the inconsistency of foundations of mathematics). Here is what you can prove: $$H_{2^{k+1}}-H_{2^k} = \sum_{j=2^{k}+1}^{2^{k+1}} \frac{1}{j} \ge \sum_{j=2^{k}+1}^{2^{k+1}} \frac{1}{2^{k+1}} = 2^{k}\frac{1}{2^{k+1}}=\frac12$$ Starting with $H_{2^0}=1$ as the base of induction, you can get $H_{2^k}\ge 1+\frac{k}{2}$.

Post No Bulls
  • 9,056