Proving n2 < 2n using Mathematical Induction

  • Thread starter skeough15
  • Start date
  • Tags
    Induction
In summary, the conversation discusses a homework problem that asks to prove the values of n where n^2 < 2n using mathematical induction. The attempt at a solution involves showing that it works for n=0 and n=1 but not for n=2,3,4, and using n=5 as the base step. It is mentioned that another induction may be needed to prove (n+1)^2 < 2(n+1). The conversation concludes with a reference to a helpful thread for solving the problem.
  • #1
skeough15
5
0

Homework Statement


We are asked to try and prove the values n where n2 < 2(n) .
It asks us to prove it by Math Induction.

The Attempt at a Solution


I can see it works for n=0 and n=1 but not for n=2,3,4 . So I made my base step n=5 and showed that 52 = 25 < 25 =32 as 25<32. I then started simple mathematical induction off by assuming that n2<2n for n>5, and tried to prove it using (n+1)2<2(n+1) but can't seem to get that proven. Any suggested help on how to prove that?
 
Last edited:
Physics news on Phys.org
  • #2


It seems that you need to show that [tex]2n+1<2^n[/tex]... Maybe another induction?
 
  • #3


yes that is exactly what I had to do, I assume it is sufficient to have an induction proof within an induction proof?
 
  • #4


I can't really see a problem with that...
 

1. What is math induction and how is it used to solve problems?

Mathematical induction is a method of proving statements or theorems in mathematics. It involves proving that a statement is true for a base case, usually the smallest possible value, and then showing that if the statement is true for any given value, it is also true for the next value. This process is repeated until the statement is proven to be true for all values.

2. How is the base case chosen when using math induction?

The base case is typically chosen based on the given problem or theorem. It should be the smallest or simplest value that the statement can be proven for. In some cases, the base case may be explicitly stated in the problem, while in others it may require some analysis to determine the appropriate value.

3. Can any problem be solved using math induction?

No, not all problems can be solved using mathematical induction. This method is typically used for problems that involve sequences, series, or polynomials. It is not suitable for all types of mathematical problems.

4. What is the difference between weak and strong induction?

Weak induction, also known as the principle of mathematical induction, involves proving that a statement is true for the base case and then showing that if it is true for any given value, it is also true for the next value. Strong induction, on the other hand, allows for multiple base cases and involves proving that if the statement is true for all values up to a given value, it is also true for the next value.

5. What are some common mistakes to avoid when using math induction?

Some common mistakes to avoid when using mathematical induction include assuming that the statement is true for all values without properly proving it, using incorrect or inconsistent variable notation, and failing to properly state and prove the base case. It is important to carefully follow the steps of math induction and double-check all calculations and proofs to avoid errors.

Similar threads

[L'Hospital's Rule] Can I Use Mathematical Induction to Prove This?
    • Calculus and Beyond Homework Help
Replies
6
Views
944
Evaluate the limit of this harmonic series as n tends to infinity
    • Calculus and Beyond Homework Help
Replies
17
Views
619
Do these two statements imply an underlying induction proof?
    • Calculus and Beyond Homework Help
Replies
7
Views
412
Proof by mathematical induction
    • Calculus and Beyond Homework Help
Replies
4
Views
1K
How to show that these sequences are summable?
    • Calculus and Beyond Homework Help
Replies
1
Views
259
Proofs By Induction: Proving P(n) for All n
    • Calculus and Beyond Homework Help
Replies
3
Views
1K
Strong Induction: Proving Every Int n>1 is a Product of Primes
    • Calculus and Beyond Homework Help
Replies
5
Views
1K
Prove every subset of countable set is either finite or else countable
    • Calculus and Beyond Homework Help
Replies
1
Views
505
Prove ##a + b = b + a## using Peano postulates
    • Calculus and Beyond Homework Help
Replies
3
Views
813
Induction Proof, Apostol Calc Vol I, I.4.4.7
    • Calculus and Beyond Homework Help
Replies
6
Views
1K

Hot Threads

Recent Insights

Back
Top