# Discrete Math Problem : Mathematical Induction

1. Mar 14, 2010

### GoGoDancer12

1. The problem statement, all variables and given/known data

Prove that H1 +H2 +...+Hn = (n +1)(Hn-n)?

2. Relevant equations

Hn denotes the nth harmonic number.

The nth harmonic number is the sum of 1+1/2+...1/n,
which is n / n +1.

I'm not really sure if Hn = (1/ n) .

Prove by Mathematical Induction

Hn denotes the nth harmonic number.

3. The attempt at a solution

Basis Step : P(1) = Hn = (n +1)(Hn-n)
(1 / n) = (n +1) ( (1 / n) -n)
(1) = ( 1 + 1) (1-1)
1 = (2) (0)
1 = 0, which is false

or
Basis Step:
P(1) = Hn = Hn = (n +1)(Hn-n)
( n / n + 1) = (n + 1) ( (n / n + 1) -1)

P(1) is false, because 1/ 2 does not equal to - 1

2. Mar 14, 2010

### jbunniii

Well, it can't be both $n/(n+1)$ and $1/n$. In fact, I don't think it is either one. As far as I know, there is no simple formula for $H_n$.

Let's start with the induction hypothesis. Namely, we need to check that the formula is correct for $n = 1$. Plugging in $n = 1$, the formula reduces to

$$H_1 = (1 + 1)(H_1 - 1)$$

Is this correct?

3. Mar 15, 2010

### GoGoDancer12

How would I know if its correct or not if there is no simple formula for H_n ??

4. Mar 15, 2010

### jbunniii

There may not be a simple formula for $H_n$ in general, but what's $H_1$? Isn't it simply 1? (Look at the defining sum.)

5. Mar 15, 2010

### GoGoDancer12

I think H1= (1 / n) = 1

6. Mar 15, 2010

### jbunniii

Right, so is the formula correct for $n = 1$? i.e. is it true that

$$H_1 = (1+1)(H_1 - 1)$$

If not, then there is something wrong with the problem statement.

7. Mar 15, 2010

### GoGoDancer12

No, its not true because Hn = 1
and (1+1)(1-1) = 0

So, there's no way to prove H1 +H2+...+Hn = (n +1) (Hn - n)
is true, right??

8. Mar 15, 2010

### jbunniii

Correct. If it isn't even true for $n = 1$ then it's certainly not a valid formula.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook