Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Strong mathematical induction, how do u figure out the range of the variable?

  1. Oct 2, 2006 #1
    Hello everyone.

    I've been looking at examples and I can't seem to see what they are doing.

    For example, the book has:

    Suppose that d1, d2, d3 ... is a sequence defined as follows:
    d1 = 9/10, d2 = 10/11.

    dk = dk-1 * dk-2 for all inegers k >= 3.

    Prove that dn =< 1 for all integers n >= 0.

    The book says:
    Proof (by strong mathematical induction): let the property P(n) be the inequality dn =< 1.

    Show that the proeprty is true for n = 1, and n =2:
    I understand why they are starting at n = 1, but why are they testing 2 cases? If i had say, d1 = 9/10, d2 = 10/11, d3 = 10/12, then would i have to test for n = 1, n = 2, and n = 3?

    They then go onto say,
    Show that for any integer k > 2, if the property is true for all integeers i with 1 =< i < k, then it is true for k:

    I'm confused on how they are getting k > 2, also how did they figure out that range from 1 = < i < k ?

    My problem looks very similar to this one, but it has 3 subscripts instead of one:

    http://suprfile.com/src/1/3itfbah/3.jpg [Broken]

    I would think k >= 3, becuase thats the problem states, that
    ek = ek -1, ek-2, ek-3 for all integers k >= 3

    Last edited by a moderator: May 2, 2017
  2. jcsd
  3. Oct 2, 2006 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    They test for two start cases because you need to specify d_1 and d_2 in order to determine the rest of the sequence. d_n is defined in terms of the two previous terms, so you're never going to infer anything about the second term from the first alone.

    Strong induction is very simple. You just use it when in order to deduce the veracity of P(n) you need to use more than just the previous term. If you can deduce it from the previous r terms for all n, then you need to verify it for the initial r terms. Note your example of d_1, d_2 and d_3 is silly. They don't satisfy d_n = d_{n-1}*d_{n-2}, do they? (please avoid using dk for the k'th term because dk-1 strictly means (dk) minus 1, not the k-1'st term).
  4. Oct 2, 2006 #3
    I do see what your saying matt,
    but i'm still confused on why they said, for any integer k > 2, when in the problem it says, k >= 3 ? or is that equivlent becuase they are integers, so they can't use for example, 2.4, they would have to use 3?
  5. Oct 2, 2006 #4

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    Of course it is equivalent. Unless you know of any integers between 2 and 3 exclusive?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook