1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Computer Science Discrete Mathematics Proof problem

  1. Mar 23, 2013 #1
    Hey guys,

    I'm taking Discrete Mathematics and am having a bit of trouble with one of my proofs. If any of you has any experience with that and could tell me where I'm going wrong, I'd appreciate it!

    Ok, here it is:

    Prove each statement in 8–23 by mathematical induction:

    27. A sequence d1, d2, d3, . . . is defined by letting d1 = 2 and
    dk = (d_(k−1)_)/k for all integers k ≥ 2. Show that for all integers
    n ≥ 1, d_n_ = 2/n!

    So here's what I got so far:

    Proof: Let d_1_, d_2_, d_3_, ... be the sequence defined by specifying that d_1_ = 2 and d_k_ = (d_(k-1)_) / k for all integers k ≥ 2, and let the property P(n) be the equation:

    d_n_ = 2 / n!

    We will use mathematical induction to prove that for all integers n ≥ 1, P(n) is true.

    Show that P(1) is true:

    To establish P(1), we must show that d_1_ = 2 / 1!

    But the left-hand side of d_1_ = 2 (by definition of d_1_, d_2, ...
    and the right-hand side = 2 / 1! which is equal to 2/1 which is equal to 2.

    Thus, the two sides of P(1) are equal, and hence P(1) is true.

    Show that for all integers k ≥ 1, if P(k) is true then P(k+1) is also true.

    Let k be any integer with k ≥ 1, and suppose P(k) is true. That is, suppose d_k_ = 2 / k!

    We must show that P(k+1) is true. That is, we must show that d_(k+1)_ = 2 / (k+1)! which is equal to 2 / k! + 1! which is equal to 2 / k! + 1.

    But the left-hand side of P(k+1) is d_(k+1)_ = d_k_ / (k+1) (By definition of sequence
    which is, by the inductive step, equal to (2/k!) / ((k+1)/1) which is equal to 2/((k!)(k+1)).

    Where do I go from there?
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted