Discrete Math Problem : Mathematical Induction

You may want to double check the problem statement and equations to make sure they are correct. In summary, the conversation discusses the problem of proving the formula H1 + H2 + ... + Hn = (n + 1)(Hn - n), where Hn is the nth harmonic number. However, there is no simple formula for Hn, and the given formula is not true even for the base case of n = 1. Therefore, it is not possible to prove the formula and there may be a mistake in the problem statement or equations.
  • #1
GoGoDancer12
14
0

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
 
Physics news on Phys.org
  • #2
GoGoDancer12 said:

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
GoGoDancer12 said:
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
GoGoDancer12 said:
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
GoGoDancer12 said:
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 to Discrete Math Problem : Mathematical Induction

What is mathematical induction?

Mathematical induction is a proof technique used to prove statements about all natural numbers. It involves proving a base case and an inductive step, which shows that if the statement holds for one number, it also holds for the next number.

When is mathematical induction used?

Mathematical induction is used when trying to prove statements about all natural numbers, such as the sum of the first n natural numbers or the properties of recursive sequences. It is particularly useful for proving statements that involve a variable n.

What is the difference between strong and weak induction?

The difference between strong and weak induction lies in the inductive step. In weak induction, the inductive step only uses the previous case to prove the next case. In strong induction, the inductive step uses all previous cases to prove the next case. Strong induction is more powerful and can be used to prove more statements, but weak induction is more commonly used.

What is the principle of mathematical induction?

The principle of mathematical induction states that if a statement holds for the first natural number (usually 0 or 1), and if it holds for n+1 whenever it holds for n, then it holds for all natural numbers.

What are some common mistakes when using mathematical induction?

Some common mistakes when using mathematical induction include not proving the base case, assuming the statement is true without using the inductive hypothesis, and using strong induction when weak induction is sufficient. It is important to carefully follow the steps of mathematical induction to avoid these mistakes.

Similar threads

Do these two statements imply an underlying induction proof?
    • Calculus and Beyond Homework Help
Replies
7
Views
453
Proof by mathematical induction
    • Calculus and Beyond Homework Help
Replies
4
Views
1K
Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
544
Induction Proof, Apostol Calc Vol I, I.4.4.7
    • Calculus and Beyond Homework Help
Replies
6
Views
1K
Proving Bernoulli's Inequality
    • Calculus and Beyond Homework Help
Replies
10
Views
2K
Prove ##|\{ q\in\mathbb{Q}: q>0 \} |=|\mathbb{N}|##.
    • Calculus and Beyond Homework Help
Replies
3
Views
587
Proofs By Induction: Proving P(n) for All n
    • Calculus and Beyond Homework Help
Replies
3
Views
1K
Weak Induction implies Strong Induction
    • Calculus and Beyond Homework Help
Replies
1
Views
1K
How to Use Mathematical Induction to Prove Equations?
    • Calculus and Beyond Homework Help
Replies
23
Views
1K
Strong Induction: Proving Every Int n>1 is a Product of Primes
    • Calculus and Beyond Homework Help
Replies
5
Views
1K

Hot Threads

Recent Insights

Back
Top