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

    Generalized mathematical induction

    Recall that the fibonacci sequence is defined as { f0=0; f1 = 1 and {fn = f n - 1 + fn -2 for n 2 Prove by generalized mathematical induction that fn = 1/sqrt(5)[ϕn - (-ϕ)-n] where ϕ = [1+sqrt(5)]/2 is the golden ratio.. (This is known as de Moivre's formula.) So...
  2. R

    What is the inductive step for proving mathematical induction?

    Hey! I've just started to learn some mathematical induction and it's proving quite tricky. Hopefully someone could help me out a little with my questions! I don't know how to format question on this forum but I'll try my best to accurately represent it: n sigma i * 2^i = (n-1) * (2^n+1) + 2...
  3. MarkFL

    Jay's question at Yahoo Answers regarding a proof by mathematical induction

    Here is the question: I have posted a link there to this thread so the OP can see my work.
  4. T

    Prove with mathematical induction

    With mathematical induction i should prove that is true for all natural numbers:http://img.tapatalk.com/d/13/10/18/u6epesu5.jpg Im sorry beacuse i have inserted an image,but I am still not used to write it in [MATH] here...
  5. J

    Mathematical induction inequality

    Homework Statement Prove; n^2 > n+1 for n = 2,3,4 by Induction Homework Equations The Attempt at a Solution p(n)= P(2) 2^2> 2+1 --> 4>3 Induction step: P(n+1): (n+1)^2 > (n+1) +1 (n+1)^2> n+2 n^2 + 2n + 1 > n+2 | -n n^2 +n + 1> 2 | -1 n^2 +n > 1 Is this correct, and how...
  6. G

    Mathematical Induction where the base case starts above 1

    Homework Statement Find all natural numbers such that 2n ≥ (1+n)2, and prove your answer. 2. The attempt at a solution I can see this is true for n=0 and n>5. I try to prove this using induction as follows 20 =1≥ 1=(1+0)2 base case: 26 =64≥ 49=(1+6)2 so it is true for n=6 and suppose 2n...
  7. matqkks

    Exploring Mathematical Induction: Impactful Examples and Real Life Applications

    Some students are not convinced that a proof by mathematical induction is a proof. I have given the analogy of dominoes toppling but still some remain unconvinced. Is there very convincing way of introducing mathematical induction? I need something which will have an impact. Are there any real...
  8. matqkks

    Is Mathematical Induction the Key to Understanding Finite and Infinite Concepts?

    Some students are not convinced that a proof by mathematical induction is a proof. I have given the analogy of dominoes toppling but still some remain unconvinced. Is there very convincing way of introducing mathematical induction? I need something which will have an impact. Are there any real...
  9. S

    Mathematical Induction on two Matrices

    Homework Statement (1 1)^n = (1 n) (0 1) (0 1) Prove this through mathematical induction. Homework EquationsThe Attempt at a Solution I've replaced n with 1, so I've done that far. Then I said k = n. Then replaced all n with (k+1). I'm really stuck...
  10. G

    Verify using Mathematical Induction

    Verify that 1(1!)+2(2!)+...+n(n!) = (n+1)! - 1 is true using induction This problem has me stumped...
  11. Y

    Prove the theorems using mathematical induction.

    Homework Statement Prove the theorems using mathematical induction. \forall n \in N, n\geq 4 \rightarrown2\leq n! Thanks in advance! Homework Equations The Attempt at a Solution First, check the base case which is n=4. \Rightarrown=4\geq4-True \Rightarrow42\leq4*3*2*1...
  12. S

    Mathematical Induction: Find P(sub2)(A(subn)) & Prove (n*(n-1))/2

    Let A(subn) = {1,2,3,...,n} For any set B, let P(subk)B=the set of all subsets of B with exactly k elements. For example, P(sub2)({1,2,3})={{1,2},{1,3},{2,3}}. A) Find P(sub2)(A(sub1)), P(sub2)(A(sub2)), P(sub2)(A(sub4)), and P(sub2)(A(sub5)) B) Use mathematical induction to prove that the...
  13. G

    Mathematical induction question

    Hi all, I am revising on Proof by mathematical induction and I have came across a question I haven't found a way to work it out. \sum_{r=1}^n r(r!) = (n + 1)! -1 I understand the steps of proving by mathematical induction question. The ! is causing the confusion.
  14. G

    How Does Series Notation Equal the Highlighted Part in Induction Proof?

    Hi all, I am so sorry I don't know whether to post this. I am revising Proof by mathematical induction Further maths using an Edexcel FP1 book. The following is from chapter 6 example 3. I know how to work Proof by mathematical induction it is part of the example that I don't understand. I...
  15. C

    Math Induction: Where Does the >2xk Come From?

    Please refer to the image attached. Where does the > 2 x k come from? Based on the proposition, shouldn't it be > k+1?
  16. J

    Mastering Mathematical Induction: Solving for the nth Term

    Homework Statement 1-1/2+1/4-1/8+...nth term= [(2^n-(-1)^n)]/3(2^(n-1))] I just can't get the nth term. I realize that the denominator should be 2^(n-1) and that, because the sign constantly changes there needs to be something like -1^n so I came up with the equation -1^n/-2^(n-1) but this...
  17. A

    Exploring the Logic of Mathematical Induction

    Hello I'm learning about proofs and in my book there's a sect. On mathematical induction. And I'm trying understand why this makes it true for all values. 1+3+5...2n-1=n^2 Suppose that the formula is known to be true for n=1, and suppose that as a result of assuming that it is true for n=k...
  18. M

    First Year Calculus Course Mathematical Induction Problem

    Prove by mathematical induction: (2n)! < (2^(2n))*(n!)^2 , for all n=2,3,4... I know that to start you must prove that it is true for n=2, (2*2)! = 24 < 64 = (2^4)(2!)^2 Then you assume that n=k and show tha n=k implies that n=(k+1) (2k)! < (2^(2k))*(k!)^2 ... At this point I...
  19. J

    Proving the Solution to a Recurrence Relation Using Mathematical Induction

    Hi all, I've been struggling with a large piece of coursework. been quite stressed latley and now I am struggling while aproaching my deadline. i need help answering this question. Use mathematical induction to show that S(n) = 3 × 2 n-1 -2 is the solution for the recurrence relation: T(n)...
  20. J

    How to prove by mathematical induction?

    How do I prove a formula/rule or something by mathematical induction? Please give me a few examples or resources and explain it as best you can because I think I'm messing up some how.
  21. T

    Proving 1 + 1/√2 +...+ 1/√n < 2√n Using Mathematical Induction

    Prove that: 1 + 1/√2 +...+ 1/√n < 2√n Work: So I've done the base case of n = 1, and I've set up the Indutive hypothesis as assuming n=k as 1 + 1/√2 +...+ 1/√k < 2√k and for the inductive step: 1 + 1/√2 +...+ 1/√k + 1/√(k+1) < 2√k + 1/√(k+1) now I'm having trouble trying...
  22. E

    How Can I Solve This Mathematical Induction Problem?

    Hello folks, I have an induction problem that I have been working on, and I am at my wit's end. If anybody could provide me with a nudge in the correct direction, I would greatly appreciate it. I have attempted to factor out a number of terms to find something remotely intuitive here to present...
  23. J

    Leibniz formula using mathematical induction

    Homework Statement Here is this problem: I have the solution http://www.proofwiki.org/wiki/Leibniz%27s_Rule/One_Variable This is where I get stuck.. Where it says: 'For the first summation, we separate the case k=n and then shift the indices up by 1.' Why does this lead to the...
  24. W

    Help with a Mathematical Induction Problem

    Suppose we want to prove that: 1/2 * 3/4 ... 2n-1/2n < 1/sqrt(3n) for all positive integers. (a) Show that if we try to prove this inequality using mathematical induction, the basis step works, but the inductive step fails.(b) Show that mathematical induction can be used to prove the stronger...
  25. C

    Can anyone solve this mathematical induction problem?

    Homework Statement Prove that for all n>1, P(n) :1 + 1/2 + 1/3 +...+1/n = k/m where k is an odd number an m is an even number.Homework Equations The Attempt at a Solution 1)Base Case n =2 P(2) = k/m 3/2 = k/m which is true. 2) Inductive Step Assume P(n) is true for some arbitrary n. 3)...
  26. L

    Proving n3 + n < 3n for n >= 4 using Mathematical Induction

    Homework Statement show n3 + n < 3n for all n >= 4 Homework Equations The Attempt at a Solution I.H : n3 + n < n for all n >= 4 3(n3 + n) < 3(3n) then (3n+1) = 3 x 3 n > 3((n3) + n ) by I.H...
  27. M

    Mathematical Induction - Algebra Manipulation

    Homework Statement I am working on a mathematical induction problem, where I need to prove: (1 - (-7) ^ (k + 2)) / 4Homework Equations (1 - (-7) ^ (k + 1)) / 4 + 2(-7) ^ (k + 1) The Attempt at a Solution So I just need to add the two items in section two above. Now I know I need a common...
  28. D

    Use mathematical induction to prove the following statements are true

    Homework Statement Use mathematical induction to prove the following statements are true for n≥1 a) 1^2+3^2+5^2+...+(2n-1)^2= [n(4n-1)]/3 Homework Equations The Attempt at a Solution Attempt at showing for n+1 is true: n[4(n+1-1)]/3+ 2[k+1-1)^2
  29. R

    Using second Principle of Mathematical Induction Proof

    Homework Statement Let F: N->N be defined by f(1)=1 and f(2)=2 and f(n+2)=1/2(f(n+1)+f(n)) Use Theorem 1.3 to prove that 1<=f(n)<=2 for all n in N Homework Equations For each n in N let P(n) be a statement about the positive integer n. If a) P(1) is true, and b) for k>1, P(k) is...
  30. A

    Understanding Mathematical Induction: Why Do We Use n Instead of k?

    what is mathematical induction? explain with an example.
  31. T

    Mathematical induction - inequality

    Homework Statement Prove that \frac{1}{n}\sum_{i=1}^n x_i\geq {(\prod_{i=1}^n x_i)}^{1/n} for positive integers n and positive real numbers x_i Homework Equations There is also a hint. It states that it does not seem to be possible to prove it directly so you should prove it for n=2^m...
  32. S

    Is f(n) = 4^n + 6n - 1 Divisible by 9 for All Positive Integers n?

    Prove that f(n) = 4^n + 6n - 1 is divisible by 9 for all positive integers of n. I've proved this by considering that f(k) is divisible by 9, i.e f(k) = 4^k + 6k -1 = 9m where m is some integer. Rearranging to give 4^k = 9m - 4k + 1 and then considering f(k+1) = 4^(k+1) + 6(k+1) - 1 then...
  33. I

    Mathematical induction with a summation in the problem.

    Hi, I'm currently taking Discrete Mathematics and I'm working on a mathematical induction problem that's a little different than usual because it has a summation in it. What I basically want to know is did I do parts A and C correctly? Homework Statement Homework Equations The Attempt at a...
  34. T

    How Many Ways to Place Divisors Around a Circle in Mathematical Induction?

    I want to now the answer of this question and I think it relates to mathematical induction. The question is: -Suppose is a natural number. In how many ways can we place numbers around a circle such that each number is a divisor of the sum of it's two adjacent numbers? Who can answer this...
  35. D

    Mathematical induction problem

    Hello! First of all I have like 5 exercises I don't quite understand so will it be a problem if I create 5 new topics in the next 24h? Homework Statement Prove, by using mathematical induction that if x+1 \geq 0 then (1+x)^n \geq 1+nx. Homework Equations The Attempt at a Solution Basic step...
  36. N

    Combinatorics - Mathematical Induction?

    Hello, I am having trouble solving this problem. Maybe I'm just overreacting to it. In my two semesters in discrete math/combinatorics, I've never seen a problem like this (with two summations) and been asked to prove it. Can some one help? \sum^{n}_{i=1} i^3 = \frac{n^2(n+1)^2}{4} =...
  37. D

    Mathematical induction problem

    Homework Statement Hello! This is I want to prove using Mathematical Induction: 1+3+5+...+(2n-1)=n^2. The problem is: I don`t understand very much about Mathematical Induction :(Homework Equations The Attempt at a Solution Suppose n=1. Then 1=1. Now suppose 1+3+5+...+(2n)=(n+1)^2. Then...
  38. D

    Proving inequality by mathematical induction

    Homework Statement I am asked to prove: 2n < (n+1)! , where n≥2 The Attempt at a Solution Base step: set n=2, then test 22 < (2+1)! 22 = 4 (2+1)!= 3! = 3(2)(1) = 6 so 4 < 6 , which is true. Induction hypothesis is 2k < (k+1)! Using this, prove 2(k+1) < [(k+1)+1]! = (k+2)! Attempt to...
  39. P

    Can Mathematical Induction Prove the Existence of a Fourth Dimension?

    I am currently exploring if whether or not a fourth dimension exists or can be drawn. According to my professor, I have to use mathematical induction. I know that 2^n is the equation and "n" equals the dimension. Therefore 2^1 is 2. The first dimension is a line with 2 terminal points...
  40. C

    Mathematical Induction problem.

    Homework Statement (1/2!)+(2/3!)+(3/4!)+...+(n/(n+1)!) a) calculate for a few small values of n. b) Make a conjecture about a formula for this expression c)Prove your conjecture by mathematical induction. Homework Equations The Attempt at a Solution So for the first part I just used values...
  41. R

    How Do You Prove Matrix Powers Using Mathematical Induction?

    Hey guys I am in precalculus right now and we just started picking up mathematical induction. Our teacher assigned us a problem that I am stumped over and I tried looking all over for a clear explanation online but I can't find anything remotely helpful. The question is: Use mathematical...
  42. R

    Proving a[n]≤2^n using Mathematical Induction

    1. Define a sequence of numbers in the following way: a[k]=a[k-1]+a[k-2]+a[k-3] for k≥3, s.t. a[0]=1, a[1]=2, a[2]=3, a[3]=6... *The numbers in brackets will be subscripts for the whole problem Prove that a[n]≤2^n using complete mathematical induction. This is what I have so far. We'll use...
  43. H

    Mathematical induction problem solving question help

    hi this question i just cannot do. i have no idea where to start: a student is trying to recall the formula for the sum of cubes of consecutive numbers. she thinks it may be (n^3(n+1)^3) /8 or (n^2(n+1)^2)/4 . show by counter example one is incorrect and the other is correct by induction...
  44. I

    Proving inequality with mathematical induction

    I am having trouble proving these. I cannot figure out how to get to the conclusion. Here is my attempt. The stuff in red is just side work and is not part of the proof. I always get stuck on these types of problems, can someone offer some tips on how to approach these kind of problems in...
  45. L

    Understanding Mathematical Induction: Clarifying Starting Points and Examples

    Hi, Some times the starting point in MA confuses me, for example (\sum_{i=1}^ni)^2=\sum_{i=1}^ni^3 have we start with 2 or it is enough to show it when n=1 Thanks in advance.
  46. W

    Mathematical Induction question

    A question I'm working on and my math book doesn't clarify the answer well enough for me to follow. I'm having some issues at getting the math symbols to work correctly so bare with me!Prove by mathematical induction that if A1, A2, ..., An and B are any n + 1 sets, then: Base step = n = 1 so...
  47. F

    Simplifying Mathematical Induction for Sequences Using Algebra

    I have an idea of what to do and I have reached the stage but when i am at final stage- I am struggling to simplify as i simply don't understand (1/2)+(2/2^2) +(3/2^3)+...+ (n/2^n) = 2 - (n+2/2^n) so I have done p(k) and p(k+1) this gives me p(k) (1/2)+(2/2^2) +(3/2^3)+...+ (k/2^k)...
  48. G

    Prove a^(m+n) = a^m + a^n with mathematical induction

    prove by induction that, 1) a^(m+n) = a^m + a^n 2) (a^m)^n=a^(mn) 2. Homework Equations -- mathematical induction 3. The Attempt at a Solution the equations hold for a = 1. let's say the equation hold for a = s; then s^(m+n) = s^m + s^n now for a = s+1; (s+1)^(m+n) = (binomial expansion of...
  49. P

    Mathematical induction problem

    Homework Statement Show that it is possible to arrange the numbers 1, 2, ... n in a row so that the average of any two of these numbers never appears between them. [Hint: Show that it suffices to prove this fact when n is a power of 2. Then use mathematical induction to prove the result when n...
  50. P

    Mathematical induction question

    Homework Statement Suppose a and b are real numbers with 0 < b < a. Show that, if n is a positive integer, then a^n - b^n \leq na^{n-1}(a-b) Homework Equations The Attempt at a Solution I'm trying to show this by induction. Let P(n) be the proposition that a^n - b^n \leq na^{n-1}(a-b)...
Back
Top