Solution to Discussion #5, Math 232

Practicing Induction Proofs

6 March 2002

Being worked on right now!

  1. An arithmetic progression is a sequence beginning with a start term a0 such that each term increases by an offset b. The terms are thus a0, a0+b, a0+2b,..., a0+ nb. Prove that for any number n, the sum of the n terms from a0 through a0+nb is (n+1)[a0+a0+nb]/2.

    Solution: Let S(n) be the sum of the n+1 terms in the progression, and let T(n) be the given formula. P(n) is then the statement "S(n)=T(n)".

    We begin by proving P(0), that S(0) = T(0). S(0) is the sum of the 0+1=1 term a0, or a0. T(0) is (0+1)[a0+ a0+0b]/2, which evaluates to a0. So S(0) and T(0) are the same number, and P(0) is proved.

    Now we let n be arbitrary and assume that S(n) = T(n). Our new goal is to prove S(n+1) = T(n+1). S(n+1) is equal to the sum S(n), plus one new term which is a0+(n+1)b. So by the inductive hypothesis, S(n+1) is equal to S(n)+a0+(n+1)b = T(n)+a0+(n+1)b.

    Substituting for T(n), we have S(n+1) = (n+1)[a0+ a0+nb]/2 + a0 + (n+1)b. Placing the last two terms over the common denominator 2 and multiplying the initial (n+1) through, we get:

    S(n+1) = [(n+1)2a0 + (n+1)nb + 2a0 + 2(n+1)b]/2 =

    [(n+2)(2a0) + (n+2)(n+1)b]/2 =

    (n+2)[a0 + a0 + (n+1)b]/2 = T(n+1).

    Since we have proved S(n+1)=T(n+1) for arbitrary n using the assumption S(n)=T(n), we have proved FORALL n: P(n) --> P(n+1). This and P(0) together complete the induction proof of FORALL n: P(n).

  2. A geometric progression is a sequence beginning with a start term a0 where each term is multiplied by a ratio r, so we have a0, a0r, a0r2,..., a0rn. Prove that if r &ne 1, the sum of these terms from a0 through a0rn is a0(1-rn+1)/(1-r).

    Solution: Once again we let S(n) be the sum and T(n) the given formula, so that P(n) states "S(n)=T(n)". To prove P(0) we evaluate S(0) as a0 (the sum of one term) and evaluate T(0) as a0((1-r0+1)/(1-r)) = a0, as long as r &ne 1. Since S(0) and T(0) are equal, P(0) is proved.

    Now we let n be arbitrary, assume that S(n)=T(n), and try to prove that S(n+1)=T(n+1). We begin by evaluating S(n+1) as S(n) plus the last term of the sum, which is a0rn+1. Then we use the inductive hypothesis to replace S(n) with T(n), giving us:

    S(n+1) = T(n) + a0rn+1 =

    a0[(1-rn+1)/(1-r) + rn+1] =

    a0[1 - rn+1 + rn+1 - rn+2]/(1-r) =

    a0[1 - rn+2]/(1-r) = T(n+1).

    Since we have proven P(n+1) from P(n) for arbitrary n, we have proven FORALL n: P(n) --> P(n+1), and this together with P(0) completes the induction proof of FORALL n: P(n).

  3. Prove that for any number n, 2n+4 is greater than (n+4)!.

    Solution: Let S(n) be 2n+4 and T(n) be (n+4)!, so that P(n) is the statement that S(n) < T(n). To prove P(0) we evaluate S(0) as 20+4=16 and T(0) as (0+4)! = 24, and since 16 < 24 P(0) is true.

    Now let n be arbitrary and assume S(n) < T(n). We must prove that S(n+1) < T(n+1). We begin by writing S(n+1) = 2n+5 as 2*2n+4 = 2S(n). By the inductive hypothesis, this is less than 2T(n). Now T(n+1) is equal to (n+5)! or (n+5)(n+4)! or (n+5)T(n). Since n is a number and hence is non-negative, we know 2 < n+5 and thus 2T(n) < (n+5)T(n) = T(n+1), and thus that S(n+1) < T(n+1). (Note that multiplying an inequality by T(n) to get an inequality requires that T(n) be positive.)

    Since we have proved P(n+1) from P(n) for arbitrary n, we have proved FORALL n: P(n) --> P(n+1) and this, together with P(0), completes the induction proof of FORALL n: P(n).

  4. Let the relation L(x,y) be defined on numbers as follows. L(x,0) is false for any number x, and L(x,y+1) is true iff either x=y or L(x,y). Using only this definition, prove "FORALL a: (a &ne 0) <--> L(0,a)" by induction on a.

    Solution: This time P(a) is the statement "(a &ne 0) <--> L(0,a)". We can think of this as "S(a) <--> T(a)", where now S(a) and T(a) are predicates. To prove P(0) we evaluate S(0), which is false as it says "0 &ne 0", and T(0), which is false because it is L(0,0) and L(x,0) is false for any x. Since both S(0) and T(0) are false, they are equivalent and P(0) is true.

    Now we assume "S(n) <--> T(n)" and try to prove "S(n+1) <--> T(n+1)". First note that S(n+1) is true, because n+1 cannot be zero as n is a number and thus is non-negative. So our goal is to prove that T(n+1), or L(0,n+1), is true. By the definition, L(0,n+1) is true iff either 0=n or L(0,n). But by the inductive hypothesis, L(0,n) is equivalent to S(n), or "n &ne 0". Thus L(0,n+1) is true iff n is equal to zero or n is not equal to zero, and it must be true.

    We have proved P(n+1) from P(n) for arbitrary n, so we have proved FORALL n: P(n) --> P(n+1) and this, with P(0), completes the induction proof of FORALL n: P(n).

Last modified 15 March 2002

David A Mix Barrington