Induction Problem

Printable View

• Jan 3rd 2007, 01:40 PM
ruprotein
Induction Problem
Prove the following statement:

(For all natural numbers n)(Summation from k=1 to n (1/k>=ln(n+1))
Some induction books use P(0) as the base case, in my book we use P(1), anybody kno how to approach?

Also we may use the fact that ln(1+x)<= x whenever x belongs to real numbers and x >=0
• Jan 4th 2007, 11:31 AM
CaptainBlack
Quote:

Originally Posted by ruprotein
Prove the following statement:

(For all natural numbers n)(Summation from k=1 to n (1/k>=ln(n+1))
Some induction books use P(0) as the base case, in my book we use P(1), anybody kno how to approach?

Also we may use the fact that ln(1+x)<= x whenever x belongs to real numbers and x >=0

Lets assume that the base case P(1) has been demonstrated.

Suppose P(n) is true,m then:

$\sum_{k=1}^n 1/k \ge \ln(n+1)$

so:

$\sum_{k=1}^{n+1} 1/k = \sum_{k=1}^{n} 1/k + 1/(n+1) \ge \ln(n+1)+1/(n+1)$

Now:

$\frac{1}{n+1}\ge \int_n^{n+1}\frac{1}{x+1}dx=\ln(n+2)-\ln(n+1)$,

so:

$\sum_{k=1}^{n+1} 1/k = \sum_{k=1}^{n} 1/k + 1/(n+1) \ge \ln(n+1)+\ln(n+2)-\ln(n+1)=\ln(n+2)$

which is what we need to complete the proof.

RonL