What is Induction: Definition and 999 Discussions

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. 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)...
  2. I_am_learning

    What is the Best Book for Learning About Single Phase Induction Motor Design?

    I want to learn about Induction Motors in detail (down to construction and design). But I currently want to emphasize on single phase induction motors and their design. I will be involved in motors repair works, so given a blank iron core of a motor, I want to be able to select wire sizes and...
  3. S

    Problem doing induction question

    Homework Statement Prove the following result using mathematical induction: 2³+4³+6³+...+(2n)³=2n²(n+1)² for all n>or=1 Homework Equations The Attempt at a Solution n=1: (2(1))³=2(1)²(2)³ 8=8 Assume n=k 2³+4³+6³+...+(2k)³=2k²(k+1)² n=k+1...
  4. W

    Proof by induction: multiplication of two finite sets.

    Homework Statement prove by induction that if A and B are finite sets, A with n elements and B with m elements, then AxB has mn elements Homework Equations AxB is the Cartesian product. AxB={(a,b) such that a is an element of A and b is an element of B} The Attempt at a Solution...
  5. W

    Fourier Transform of a Free Induction Decay Signal

    Homework Statement S(t) = S(0)e^{-i \pi f_{o}t} e^{-t/T^{*}_{2}}, 0 \leq t < \infty S(t) = 0, t < 0 Show that the spectrum G(f) corresponding to this signal is given by: G(f) = S(0) { \frac{T^{*}_{2}}{ 1 + [2 \pi (f- f_{o} )T^{*}_{2}]^{2}} + \frac{i2 \pi (f- f_{o} )...
  6. S

    How to show sequnce is divergent (math. induction)

    Homework Statement For the sequnce an defined recursively, I have to determine the limiting value, provided that it exists. a1=2 and a(n+1) = 1/(an)^2 for all n Homework Equations The Attempt at a Solution Ok, so I 've done problems like this but the a(n+1) was biggger than...
  7. R

    Use an Induction Cooktop at different power supply's frequencies?

    Hi everybody, I want to buy a 3kW induction cooktop. The one I intend to buy requires a power source at 220V/60Hz. However, in my country, the main power is 220V/50Hz. Does this difference in frequency cause any incompatible problems? Can I use the induction cooktop in my country? Thanks.
  8. mnb96

    Question on a proof by induction

    Hello, I have a subgroup S=\left\langle A \right\rangle generated by the set A, i.e. S=\left\{ a_1 a_2 \ldots a_n \;|\; a_i \in A \right\}. When I need to prove by induction on n some property of S, what should I choose as the base case of induction? n=1, or simply n=0 ? If the answer is n=0...
  9. 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...
  10. P

    Faraday's Law of Induction - Current in Multiple Wires

    Homework Statement A 7.40 cm diameter coil consists of 15 turns of circular copper wire 2.3 mm in diameter. A uniform magnetic field, perpendicular to the plane of the coil, changes at a rate of 7.29×10^−3 T/s . Determine the current in the loop. Express your answer using two significant...
  11. M

    Binomials and Proof by Induction

    Homework Statement Prove (n choose k) ≤ ((en)/k)^k by induction on k. Homework Equations I can't of anything that's awfully relevant besides the general steps of induction. The Attempt at a Solution So I found it true for the k=1 case which was easy enough. Then assumed true...
  12. 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...
  13. T

    Proof by Induction: Solve Complex Variables Problem 12

    I'm having a little bit of difficulty with proofs by induction. I believe I understand the principles behind induction but find that I often get "stuck" in my proof - and I can "see" that its true but am not sure how to get that one step that will finish the proof. When using mathematical...
  14. I

    Proving 3^n >= 2n+1 by Induction

    Homework Statement Prove that 3^n >= 2n+1 for all natural numbers. Homework Equations 3^n >= 2n+1 [is bigger or equal to] The Attempt at a Solution 3*1>=2+1 True for n=1 Assumption: 3^k>=2k+1 3^(k+1)>=2k+3 3^k*3>=2k+3 (2k+1)*3>=2k+3 <---can I just substitute 2k+1...
  15. Z

    Proof of an inequality involving a series (probably by induction)

    u_{n} = \sum_{k=1}^{n}\frac{1}{n+\sqrt{k}} Proof that: \frac{n}{n+\sqrt{n}} \leq u_{n} \leq \frac{n}{n+1} Ok, I've been working on that problem for about two hours now and I still don't have a clue how to proof this inequality. I guess it should be done by induction, but I have problems...
  16. 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
  17. V

    Proving the Induction Relationship: 1 = 1, 1 - 2^2 = -(1+2), and More!

    1 = 1 1 - 2^2 = -(1+2) 1 - 2^2 + 3^2 = (1+2+3) 1^2 - 2^2 + 3^2 - 4^2 = -(1+2+3+4) and so on. I have to prove that this relationship is true for all natural numbers. This is what I did: clearly it is true for 1, 2, 3 and 4. assume true for n odd: 1^2 - 2^2 + 3^2 - 4^2 ... + n^2 = (1 + 2 + +3...
  18. D

    Induction: 1+2+2^2+2^3+ +2^n-1=2^n-1

    1. Homework Statement [/b] Use mathematical induction to prove the following statements are true for all integers n≥1 1+2+2^2+2^3+...+2^n-1=2^n-1 Attempt at a solution: For n=1 1+2^(1-1)=2^1-1 1=1 ∴ it is true. Let Sn=Sk If it is true for k, it must also be true for...
  19. C

    Induction to demonstrate n-1 is a natural number

    The question is as follows: Using an induction argument if n > 1 is a natural number then n-1 is a natural number. P(n)=n-1 such that n-1 is a natural number Following the steps: Base case: n=2, P(2)=1 which is a natural number. We fix a natural number n and assume that P(n)=n-1 is...
  20. P

    Induction: prove x^n + 1/x^n = 2cos(n*theta)

    Homework Statement If a and theta are real numbers such that x + 1/x = 2cos(theta), then: x^n +1/x^n = 2cos(n*theta) Homework Equations x + 1/x = 2cos(theta) The Attempt at a Solution So I was able to show that the statement was true for n=1, but I'm stuck on how to even start...
  21. J

    Math Olympiad problem - Applying induction and the pigeon hole principle

    Ok, so this problem looks like an induction problem to me, so I used that, but I only got as far as the induction hypothesis. The hint says to use the pigeon hole principle. I'm not sure how to use that for this problem.
  22. S

    Proving n! is Greater than n^2 and n^3: Induction Proof for Integers

    Homework Statement Prove that n! > n2 for every integer n ≥ 4, whereas n! > n3 for every integer n ≥ 6. Homework Equations See above. The Attempt at a Solution Ok, I am attempting an induction proof, but I seem to be stuck in the following step. In any case, I don't even know if...
  23. 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...
  24. M

    V/f speed control of 3 phase Induction motors

    When the voltage / frequency is maintained constant in 3 phase Induction motor i.e. flux is maintained constant by changing the voltage and frequency in same proportion, What is the torque proportionality equation. Whether Torque is proportional to Slip X Frequency or Torque is...
  25. R

    Magnetic Induction and Magnetic Field

    Homework Statement I would appreciate some help with the following problem: http://img407.imageshack.us/img407/7647/questionb.jpg Homework Equations This is an equation derived from Biot-Savart law: B= \frac{\mu_0 I}{4 \pi s} \int^{\theta_2}_{\theta_1} cos \theta d \theta =...
  26. W

    Electrostatic Induction and Spray Painting

    Hi, What is the charge on a droplet of paint? Im trying to understand what's going on in electrostatic spray painting - specifically at the spray nozzle (this could also be crop spraying too) My understanding so far is that a paint supply is fed into a grounded nozzle. An electrode...
  27. S

    Electromagnetic induction on iron core question

    Homework Statement An iron core with a solenoid coiled around it is in a circuit with a switch and a dc current supply. In front of it, there is a iron ring tied to the ceiling such that it faces the solenoid without touching the circuit. When the switch is turned on what is observed and...
  28. A

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

    what is mathematical induction? explain with an example.
  29. Reckoner

    MHB Induction Proof of Inequality Involving Summation and Product

    I'm reading "An Introduction to Mathematical Reasoning," by Peter Eccles. It has some interesting exercises, and right now I'm stuck on this one: "Prove that \[\frac1n\sum_{i=1}^nx_i \geq \left(\prod_{i=1}^nx_i\right)^{1/n}\] for positive integers \(n\) and positive real numbers \(x_i\)."...
  30. P

    Does induction sometimes allow false statements to be proven correctly?

    :smile: so i was reading an old thread that mentioned the following problem from Apostol's Calculus I I'm not sure if I my solution is correct, so I am posting it here for opinions: The inductive step is correct, i.e. if it can be shown that the theorem holds for n=3, then the theorem is...
  31. A

    Creating a PM Induction Generator from Induction Motor

    Hello this is my first post, please let me know if I'm breaking any rules, I'm still a bit hazy on them. I am in the process of making a permanent magnet induction generator from and old washing machine induction motor. The motor is rated 1725 rmp, 115 volts 6.3 amps at 1/3 horsepower. It is...
  32. L

    Using Induction to prove something false?

    Howdy, I am clumsy at best with induction (pretty new to it sadly), and I was wondering if it's proper to prove something false with induction? Every time I've used induction it's always been to prove something true. It may be a dumb question, but I'm beginning to think induction is only for...
  33. Chris L T521

    MHB POTW: Proving Group Theory Induction & SO(2, $\mathbb{R}$) Isomorphism

    Thanks to those who participated in last week's POTW! Here's this week's problem (I'm going to give group theory another shot). ----- Problem: (i) Prove, by induction on $k\geq 1$, that \[\begin{bmatrix}\cos\theta & -\sin\theta\\ \sin\theta & \cos\theta\end{bmatrix}^k =...
  34. 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...
  35. L

    Induction Proof - show 2^n = sum of nCi (i = 0 to n)

    Homework Statement Hi everyone, In my assignment I've been asked to show that 2^n = Ʃ(nCi) i from 0 -> n ie: 2^n = nC0 + nC1 + ... + nCn and I have to do this by induction and then also by a combinatorial argument. Homework Equations Right now I'm just working on the induction part...
  36. B

    Can you use induction on n cases (as opposed to infinity)?

    Homework Statement this is probably a dumb question, but I'm doing this proof where i have to show two sets are equal, where each set is a union from 1 to n sets. this is pretty easy to show with induction, i think, but I'm used to using induction when i have an infinite amount of things, so...
  37. 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...
  38. O

    Electromagnetic induction problem

    Homework Statement http://imageshack.us/photo/my-images/194/55132039.png/ http://imageshack.us/photo/my-images/194/55132039.png/ How much curret flows trough circuit ABCD when the center of the circuit (O) is distance r from the straight wire? I think these are the relevant equations...
  39. A

    Set theory: strong induction

    I am interested in a little fun... It has been some time since I have done any set theory, and I am forgetting the symbols and ideas... So, I wanted to construct a strong inductive proof, and get a bit of help with how to concisely write the proof, and how to get TEX here at the forums to...
  40. D

    Using a Squirrel Cage Motor in an Induction Generator

    I'm not sure whether to post here or EE forum, if it is better suited there, please advise/assist in moving it. I'm familiar enough with Induction, though not practiced in the formulae describing it. I recently came into need of an AC generator and thought there has to be some useful...
  41. U

    Binomial Theorem proof by induction, Spivak

    Homework Statement Prove the binomial theorem by induction. The attempt at a solution http://desmond.imageshack.us/Himg35/scaled.php?server=35&filename=sumu.png&res=landing Hi, running into trouble with this proof and google hasn't helped me. I don't understand the jump here, and as...
  42. P

    Bridge rectifier based mains (line) frequency doubler for an induction motor

    I want to get a larger flow rate out of a common 3 speed induction motor desk fan. Without forking out for an off the shelf VFD, I thought perhaps I could build a frequency doubler using a bridge rectifier. Following the circuit from left to right, I'm thinking that I'll feed the 240V...
  43. S

    Electromagnetic induction near a generator

    Hi , i am a high school student ( class 10 ) and after reading about electromagnetic induction iwas thinking about what if u place a wire coil connected to a circuit in the magnetic field / near a generator ? Because electricity is turned of for a fraction of a second there will be great...
  44. D

    Electrical Generators; Excitation/Self induction start up

    Smaller generators are sometimes self-excited, which means the field coils are powered by the current produced by the generator itself. The field coils are connected in series or parallel with the armature winding. When the generator first starts to turn, the small amount of remnant magnetism...
  45. A

    MHB Proving solution to recurrence equation using induction

    Hello, I have the following recurrence equation $$T(n)=aT(n-1)+bn$$ Using substitution, I have solved it to the following form $$T(n)=a^{n-1}+b \sum_{i=2}^{n}ia^{n-i}$$ Now I am trying to prove my solution is correct using induction, but I'm a bit lost. Any advice on how to conduct this...
  46. Hercuflea

    Math induction - I think i totally missed the point of it.

    Homework Statement "Use strong induction to show that every positive integer n can be written as a sum of distinct powers of two, that is, as a sum of a subset of the integers 2^{0} = 1, 2^{1} = 2, 2^{2}= 4, and so on. [Hint: for the inductive step, separately consider the case where k+1...
  47. 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...
  48. 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...
  49. H

    Transfinite Induction: Understanding & Examples

    I'm a bit confused on the subject of transfinite induction. I've read that it is equivalent to usual induction on the ordinal number ω (presumably a proof of this can be found in a standard book on the subject - any suggestions?) Does anyone have an example of a case in which this isn't true...
  50. 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...
Back
Top