Mathematical induction Definition and 218 Threads

Mathematical induction is a mathematical proof technique. It is essentially used to prove that a statement P(n) holds for every natural number n = 0, 1, 2, 3, . . . ; that is, the overall statement is a sequence of infinitely many cases P(0), P(1), P(2), P(3), . . . . Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder:

Mathematical induction proves that we can climb as high as we like on a ladder, by proving that we can climb onto the bottom rung (the basis) and that from each rung we can climb up to the next one (the step).
A proof by induction consists of two cases. The first, the base case (or basis), proves the statement for n = 0 without assuming any knowledge of other cases. The second case, the induction step, proves that if the statement holds for any given case n = k, then it must also hold for the next case n = k + 1. These two steps establish that the statement holds for every natural number n. The base case does not necessarily begin with n = 0, but often with n = 1, and possibly with any fixed natural number n = N, establishing the truth of the statement for all natural numbers n ≥ N.
The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion. Mathematical induction is an inference rule used in formal proofs, and in some form is the foundation of all correctness proofs for computer programs.Although its name may suggest otherwise, mathematical induction should not be confused with inductive reasoning as used in philosophy (see Problem of induction). The mathematical method examines infinitely many cases to prove a general statement, but does so by a finite chain of deductive reasoning involving the variable n, which can take infinitely many values.

View More On Wikipedia.org
Recent contents Top users
  1. P

    Mathematical Induction (The inductive step)

    1. I don't understand how to prove this. for all n≥1, 10n - 1 is divisible by 9. 3. I've done the basis step. Now I'm on the inductive step. I'm using (10k+1-1)/9=1. I don't know where to go from there. Using algebra just gets me down to 10k+1= 10. And I really don't think that's...
  2. D

    How can I prove that n^3 + (n+1)^3 + (n+2)^3 is a multiple of 9?

    Hello everybody, I am doing my reading lately to prepare for some exams to join a mathematics department. And I would very much like, if anyone could help, the solution (or a hint) to the following induction proof. " Show that n^3 + (n+1)^3 + (n+2)^3 is a multiple of 9 " :smile: I...
  3. Z

    Mathematica Hard mathematical induction question

    Hi everyone, I have been trying to do this induction question... but can't seem to understand how to do it. Prove by induction that, for all integers n is greater than or equal to 1, (n+1)(n+2)...(2n-1)2n = 2^n[1x3x...x(2n-1)] This is what someone else has given as the answer: For n...
  4. H

    Mathematical Induction Problem: Finding a Formula for a Sequence of Numbers

    Homework Statement Okay, so I'm going to be completely honest, I am really bad at math, and I have been struggling the past couple of weeks in my Quantitative Reasoning class. I am so lost. I don't know if it's my teacher's teaching method or what, but nothing is clicking for me at the moment...
  5. T

    Proving r^n > r^m through mathematical induction

    Homework Statement I need to prove that for any real number r, if 0 < r < 1, then for all positive integers n and m, if n < m, then r^n > r^m. Homework Equations No calculus techniques are permitted, only mathematical induction. The Attempt at a Solution I know that any...
  6. A

    Understanding Mathematical Induction: Proving Implications and When to Use It

    Hello, I have a question about inductive reasoning... Earlier this week my intro proofs class went over the logical structure of induction, and an example. The example was a proof of \Sigmai = n*(n + 1)/2 My main issue is the assumption that "p(k)" is true. What if it's not? I asked this in...
  7. A

    Understanding Peano's Axioms: The Role of Mathematical Induction

    I'm having a bit of trouble understanding why the principle of induction is included as one of Peano's axioms. It seems like it should not be independent of the others. Obviously it can be stated as: If a predicate P is true only of natural numbers, P(0) is true, and also P(n)\rightarrow...
  8. 2

    Mathematical induction problem.

    Hi. I am learning mathematical induction on my own and I came across this problem: Homework Statement Prove: 1*4 + 4*7 + 7*10 + ... + (3n - 2)(3n + 1) = n(n + 1)²2. The attempt at a solution Quick test for n=1: (3 -2)(3 + 1) = 1(1 + 1)² 4 = 4 Alright, so I rewrite this with, on the left...
  9. B

    Mathematical Induction: Power Rule for Differentiation

    Homework Statement Prove that \frac{d}{dz}z^n = nz^{n-1}\;\;\; \forall n\in\mathbb{N} using the Product Rule for differentiation and mathematical induction. Homework Equations \frac{d}{dz} f(z) = \lim_{\Delta z\to 0} \frac{f(z+\Delta z) - f(z)}{\Delta z} \frac{d}{dz}[f(z)g(z)] = f\,'(z)g(z) +...
  10. B

    Is 11^n - 4^n a Multiple of 7? Proving with Mathematical Induction

    Homework Statement Prove that 11^n - 4^n is a multiple of 7 Homework Equations N/AThe Attempt at a Solution I substituted k+1 in for n and simplified to get 11(11^k)-4(4^k) but after this point I get stuck. Any help would be appreciated.
  11. J

    Mathematical induction w/ Summation question

    Homework Statement Summation of i(i + 1) (with i going from i = 2 to i = n-1) = n(n-1)(n=1) / 3 a. Write P(2). Is P(2) true? b. Write P(k) c. Write P(k+1) d. Prove by mathematical induction that the formula holds true for all integers n \geq 2 Homework Equations...
  12. P

    Mathematical Induction Problem

    I was working on my homework and I did two of the mathematical induction problems before this one and they were super easy but I must be forgetting something because I just can't seem to solve this one. 2+7+12+17...+(5n-3) = (n/2)(5n-1) So I know that step 1 is to prove that it works with...
  13. P

    Proving by Mathematical Induction

    so the problem is 3+7+11+15+...+(4n-1) = n(2n+1) so I know that step 1 is to plug in 1 for the right side and check that it equals three... 3=1(2(1)+1) and yes it equals 3 Then I know that you assume that 3+7+11+15+...+(4n-1) = n(2n+1) The next step is where I get confused I know that...
  14. V

    Mathematical induction proof concerning polynomials in Z2.

    Homework Statement For each n\,\in\,\mathbb{N}, let p_n(x)\,\in\,\mathbb{Z}_2[x] be the polynomial 1\,+\,x\,+\,\cdots\,x^{n\,-\,1}\,+\,x^n Use mathematical induction to prove that p_n(x)\,\cdot\,p_n(x)\,=\,1\,+\,x^2\,+\,\cdots\,+x^{2n\,-\,2}\,+\,x^{2n}Homework Equations Induction steps...
  15. Y

    Mathematical Induction with an Inequality

    Homework Statement Prove that (n + 1)n - 1 < nn for n ∈ Z+. [Hint: Induction is suggested. Write out the induction statement explicitly. Make one side of the inequality look like your induction hypothesis.] Homework Equations The Attempt at a Solution ^ That's what I have so far. I'm good...
  16. G

    Proof by Mathematical Induction

    Homework Statement Prove: 1+2(2+3+4+···+n)+(n+1)=(n+1)2-1 for all n within NHomework Equations PMI The Attempt at a Solution I tried applying PMI starting with the basis step, allowing n=1, assuming the equation would be true. However 1+2(1)+(1+1)=?=(1+1)2-1 yields 5=?=3 which is false. The...
  17. E

    Proof By Mathematical Induction

    Homework Statement Use mathematical induction to prove the following statement. n \geq 2,~ \sum_{k=1}^{n} \frac{1}{k^2}~<~1-\frac{1}{n} Homework Equations The Attempt at a Solution This is the third problem I've done of this type, so I am by no means an expert. So this attempt may be...
  18. pairofstrings

    What is the use of mathematical induction

    In the context of Set theory and Relations why do we use mathematical induction. Is there any deep relation between all these concepts or mathematical induction is only a separate concepts introduced in the textbooks after Sets and Relation ; Functions ; and then Mathematical induction.
  19. T

    Mathematical Induction am I on the right track?

    Homework Statement The sequence a0 -> n is defined by ai = b+i*c. Prove by induction on n that the sum of the terms in the sequence is (n+1)(a0 + an)/2.Homework Equations The Attempt at a Solution I defined predicate P(n) as (n+1)(a0+an)/2. My goal is P(n+1), which is (n+2)(a0+an+1)/2. I...
  20. K

    Mathematical Induction Problem

    Homework Statement Prove that \frac{1}{\sqrt{1}}+\frac{1}{\sqrt{2}}+...+\frac{1}{\sqrt{n}}\geq\sqrt{n} for all n \in N Homework Equations The Attempt at a Solution p(1): \frac{1}{\sqrt{1}} = \frac{1}{1} = 1 = \sqrt{1} \geq \sqrt{1} Let \frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} +...+...
  21. A

    Proving x_n+1 > x_n with Mathematical Induction | Real Number Sequence

    Homework Statement Consider the sequence of real numbers x1, x2, x3,... defi ned by the relations x1 = 1 and xn+1 =\sqrt{1 + 2xn} 1. Use mathematical induction to show that xn+1 > xn for all n \geq 1. The Attempt at a Solution I'm a bit thrown off by this question because it...
  22. N

    Need an opinion on this solution involving mathematical induction

    Hey guys, this is a problem given to us by our professor in one of the worksheets. I would like an opinion to see if this proof is valid Homework Statement Use mathematical induction to prove that 3^{n}+7^{n}-2 is divisible by 8 for \foralln\inZ^{+}Homework Equations Base step: n=0...
  23. S

    Can you Prove that {2}_{}an+1 = _{}an _{}an+2 =(-1)n for the Fibonacci series?

    Mathematical induction...please help me! _{}a1 =1, _{}a2 =1,_{}a3 =2,_{}a4 =3..._{}an = _{}an-1 + _{}an-2 is a Fibonacci series...Prove That ^{2}_{}an+1 = _{}an _{}an+2 =(-1)n
  24. M

    Mathematical Induction problem

    Im practicing inductions on my own and I am getting stuck on one in particular... S_n = \frac{3(3^n-1)}{2} for a_n = 3^n I know that S_1 = 3 when you plug 1 into the equation, because it is the first term in the sequence Therefore, S_1 = a_1 = 3 I need to prove then S_{n+1} =...
  25. B

    How Does the Inequality 2*3^k >= 3 Arise in Mathematical Induction?

    Hi, I'm trying to learn mathematical induction for proving inequalities, but there is just one step I cannot get past: finding another inequality that is added to the inductive hypothesis. For example, in this problem: Prove for all positive integers (n >= 1), prove 3^n + 2 >= 3n. I...
  26. B

    Proving f(n) = 5 x 3^n - 4 with Mathematical Induction

    Homework Statement Let f(n + 1) = 3f(n) + 8, with f(1) = 11. Prove by induction that f(n) = 5 x 3^n - 4.Homework Equations The Attempt at a Solution I don't even know where to start! Any help would be appreciated. Thanks. :-)
  27. N

    Use mathematical induction to prove:

    Please help! Use mathematical induction to prove.
  28. P

    REAL ANALYSIS, Mathematical Induction

    Homework Statement What is wrong with my solution?... I don't quite understand where do I go from there... Homework Equations The Attempt at a Solution
  29. P

    Difference between Strong Induction and Mathematical Induction?

    Homework Statement Explain the difference between The principle of Mathematical Induction and The principle of Strong Induction. One is easier than the other. Why? Homework Equations The Attempt at a Solution My book says that they are in fact identical. Proofs are almost the...
  30. F

    Mathematical Induction problem

    I'm trying to solve this problem from CH2 of spivak's calculus of which I am self-studying. Homework Statement Prove the following by mathematical induction: 1^3+...+n^3=(1+...+n)^2 Homework Equations To prove by mathematical induction, you test whether P(1) is true and if P(k) is...
  31. T

    Inequality Mathematical Induction

    Homework Statement Prove the Inequality for the indicated integer values of n. n!>2^n,n\geq4 Homework Equations The Attempt at a Solution For n=4 the formula is true because 4!>2^4 Assume the n=k k!>2^k Now I need to prove the equation for k+1 I can multiply both sides by 2 and have...
  32. T

    Proving the Formula Using Mathematical Induction

    Homework Statement Use mathematical induction to prove the formula for every positive integer n. \sum_{i=1}^{5}i^5=\frac{n^2(n+1)^2(2n^2+2n-1)}{12} Homework Equations The Attempt at a Solution I know this will be true because the RHS is just your standard sums of powers of...
  33. K

    Can Mathematical Induction Prove Theorems for Negative Numbers?

    Is the principle of mathematical induction unable to prove theorem of negative numbers?
  34. K

    Can the strong form of mathematical induction always be used?

    Can i use the strong form every time? Why do people still use the ordinary form?
  35. Z

    How can we prove that p(n) is true for all integers n with 1 <= n < v.size()?

    I cannot get my head around this at all. Suppose that v is of type Vector of Integers and we know the following:- 1. v is sorted. 2. No two items in v are the same. 3. v.at(1) is 12. For an integer n, where 1 <= n <= v.size(), let p(n) be the following proposition: p(n): v.at(n) => 11...
  36. E

    Mathematical induction and arithmetic progression

    Homework Statement All the terms of the arithmetic progression u1,u2,u3...,un are positive. Use mathematical induction to prove that, for n>= 2, n is an element of all positive integers, [ 1/ (u1u2) ] + [ 1/ (u2u3) ] + [ 1/ (u3u4) ] + ... + [ 1/ (un-1un) ] = ( n - 1 ) / ( u1un)...
  37. M

    Help with simple proof by mathematical induction

    Homework Statement prove: 0^2 + 1^2 + 2^2 + ... + n^2 = n(n+1)(2n+1)/6 Homework Equations The Attempt at a Solution I'm confused on how to prove this by induction. I'm not exactly sure what the goal of the rearrangement is after substituting (n+1). Any help is much...
  38. A

    Can 2^n Always Be Greater Than n for Natural Numbers?

    Homework Statement Prove that for all the natural numbers n that 2^n > n Homework Equations The Attempt at a Solution Base Case is easy Then the inductive step you have 2^k > k as the inductive hypothesis show that p[k+1] holds 2^(k+1) > k+1 on the left side 2^(k+1) = 2^k * 2...
  39. M

    Mathematical Induction on rationals

    Hi I'm a high school student. I gave a proof for the following theorem, but I was told by some professors that this is trivial and using natural induction twice for the rationals will do the same thing. What do you think? Is it just redundant? Theorem: Let P(r) be a statement about r...
  40. G

    Discrete Math Problem : Mathematical Induction

    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...
  41. A

    Mathematica Proving 1/2 Series Converges Using Mathematical Induction

    (a) Give a recursive definition of the set P of all non negative integers, (b) formulate the applicable induction principle and (c) then apply the induction principle to prove that 1/2^0+1/2^1+1/2^2...+1/2^i = 2-1/2^n for n>=0 I have solved parts a and b and stuck on c (a) P is the...
  42. M

    Proving 2^n>=(n+1)^2 by mathematical induction

    Hello, In this problem I am trying to Determine the exact set of natural numbers n for which the inequality 2^n>=(n+1)^2 holds. (equation (1)) I have already dealt with the base case where n=6, (since the inequality does not hold for n<6), and so (1) holds for n=k, and I need to show that it...
  43. A

    Prove Inequality by Mathematical Induction

    Homework Statement \forall n \in Z^+, \sum_{i=1}^n \frac{\sqrt{i+1}}{2i} > \frac{\sqrt{n}}{2} Homework Equations I have to prove the above via mathematical induction. The Attempt at a Solution I did the base case, n = 1 and found it true for the base case. Then I assumed that...
  44. C

    Using the method of mathematical induction

    -------------------------------------------------------------------------------- 1. Homework Statement Let H be a ten- element set of potive integers ranged from 1 to 99. Prove that H has two disjoint subsets A and B so that the sum of the elements of A is equal to the sum of the elements of B.
  45. C

    Using the mathod of mathematical induction

    Homework Statement Let H be a ten- element set of potive integers ranged from 1 to 99. Prove that H has two disjoint subsets A and B so that the sum of the elements of A is equal to the sum of the elements of B.
  46. K

    Mathematical induction: Fibonacci numbers

    Homework Statement The Fibonacci numbers are defined by f(1)=1, f(2)=1 and for n>2, by f(n) = f(n-2) + f(n-1). Prove by mathematical induction that f(3n) is even for all natural numbers n. Proof: Base case: (n=1) f(3) = f(2)+f(1) =1+1 =2 is even Induction hypothesis: (suppose the...
  47. D

    Mathematical Induction: Chapter 1, Example 4 from WiM? by Courant

    This is not homework, per se, but I have recently started reading Courant and Robbins' What is Mathematics? Homework Statement Prove by mathematical induction. (1+q)(1+q2)(1+q4) ... (1+q2n) = (1-q2n+1) / (1-q) Homework Equations Only the problem itself.The Attempt at a Solution Using the...
  48. S

    Help with Mathematical Induction

    Homework Statement Prove by matematical induction that (2^(n+1)+9(13^n)) divides by by 11 for all positive intergers Homework Equations The Attempt at a Solution I really have no idea where to start...
  49. J

    Is mathematical induction a deductive or inductive argument?

    Homework Statement Is mathematical induction a deductive or inductive argument? Would appreciate the help. Thanks. Jeremy Homework Equations The Attempt at a Solution Its name suggests that the process is inductive, yet I know all of mathematics depends on deductive reasoning...
  50. James889

    Proving \sum_{i=0}^n (i-3) \geq \frac{n^2}{4} with Mathematical Induction

    Hi, I need some help with mathematical induction The question is as follows: prove that \sum_{i=0}^n (i-3) \geq \frac{n^2}{4} I have shown that it holds for the base step where n=12 \frac{144}{4} = 36 and the sum of all the i's up to 12 -3,-2,-1,0,+1,+2,+3,+4,+5,+6,+7,+8,+9 = 39...
Back
Top