• Support PF! Buy your school textbooks, materials and every day products Here!

Discrete Math Problem : Mathematical Induction

  • #1

Homework Statement



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

Homework 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.

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
 

Answers and Replies

  • #2
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179

Homework Statement



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

Homework 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) .
Well, it can't be both [itex]n/(n+1)[/itex] and [itex]1/n[/itex]. In fact, I don't think it is either one. As far as I know, there is no simple formula for [itex]H_n[/itex].

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

[tex]H_1 = (1 + 1)(H_1 - 1)[/tex]

Is this correct?
 
  • #3
How would I know if its correct or not if there is no simple formula for H_n ??
 
  • #4
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
How would I know if its correct or not if there is no simple formula for H_n ??
There may not be a simple formula for [itex]H_n[/itex] in general, but what's [itex]H_1[/itex]? Isn't it simply 1? (Look at the defining sum.)
 
  • #5
I think H1= (1 / n) = 1
 
  • #6
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
I think H1= (1 / n) = 1
Right, so is the formula correct for [itex]n = 1[/itex]? i.e. is it true that

[tex]H_1 = (1+1)(H_1 - 1)[/tex]

If not, then there is something wrong with the problem statement.
 
  • #7
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
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
179
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??
Correct. If it isn't even true for [itex]n = 1[/itex] then it's certainly not a valid formula.
 

Related Threads for: Discrete Math Problem : Mathematical Induction

Replies
5
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
900
  • Last Post
Replies
1
Views
1K
Top