Scribd Logo
Upload

Welcome to Scribd!

  • 9 views

    Tutorial 03 Bic 10103

    Uploaded by

    Atiqah Baharuddin
    The document provides examples and questions about proving formulas using mathematical induction. It includes examples of basic induction steps and proving summation formulas by induction. Questions cover topics like replacing variables, basic induction steps, proving formulas, and showing divisibility using induction.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Tutorial 03 Bic 10103

    Uploaded by

    Atiqah Baharuddin
    9 views3 pages
    The document provides examples and questions about proving formulas using mathematical induction. It includes examples of basic induction steps and proving summation formulas by induction. Questions cover topics like replacing variables, basic induction steps, proving formulas, and showing divisibility using induction.

    Original Description:

    stuktur diskrit tutorial

    Original Title

    tutorial03bic10103.docx

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document provides examples and questions about proving formulas using mathematical induction. It includes examples of basic induction steps and proving summation formulas by induction. Questions cover topics like replacing variables, basic induction steps, proving formulas, and showing divisibility using induction.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    9 views3 pages

    Tutorial 03 Bic 10103

    Uploaded by

    Atiqah Baharuddin
    The document provides examples and questions about proving formulas using mathematical induction. It includes examples of basic induction steps and proving summation formulas by induction. Questions cover topics like replacing variables, basic induction steps, proving formulas, and showing divisibility using induction.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 3

    Subject Code BIC 10103 Item No.

    Tutorial 03

    FSKTM
    Subject Discrete Structure Date 01/10/2023

    Objective : To enhance the skill of Induction.

    NAME : …………………………………………………….
    MATRIC NO.: …………………………………………………….

    Example: Prove the following formula by induction:

    n ( n+ 1 )
    1+2+3+ ⋯ +n=
    2

    Solution:

    1 ( 1+1 )
    1=
    Step 1: Ifn=1 , ∴ P 1 is true since 2

    Step 2: If Pk is true, then

    k ( k +1 )
    Pk :1+2+3+ ⋯ + k=
    2
    k ( k +1 )
    Pk +1 :1+2+3+ ⋯ +k + [ ( k +1 ) ] = + [ ( k +1 ) ]
    2
    k ( k +1 ) +2 ( k +1 )
    =
    2
    2 2
    k +k + 2 k+ 2 k +3 k +2
    = =
    2 2
    ( k +1 ) ( k +2 )
    =
    2
    ∴ P n is true for all natural numbers n .
    Question 1: Replacing k with k +1 in an algebraic expression

    Replace k with k +1 in the following:


    k
    a) 3 −1
    k +1
    b) 4 −2
    2
    c) k +2 k
    k
    d) ( k +1 )
    2
    e) ( k + 2k )

    Question 2: Basic of induction steps

    Let P(n) be the statement that 12 + 22 + ··· + n2 = n(n + 1)(2n + 1)/6 for the positive
    integer n.

    a) What is the statement P(1)?


    b) Show that P(1) is true, completing the basis step of the proof.
    c) What do you need to prove in the inductive step?
    P(k) →p(k+1) for k≥ 1 is true statement.

    Question 3: Proving a summation formula by induction

    Prove that 12 + 32 + 52 + ··· + (2n + 1)2 = (n + 1)(2n + 1)(2n + 3)/3 whenever n is a


    nonnegative integer.

    Question 4: Proving a formula by induction

    Prove the following formula by induction:

    2+ 4+ ⋯ +2 n=n ( n+ 1 )

    Question 5: Proving a formula by induction

    3
    Use mathematical induction to show that 3 divides n +2 n whenever n is a
    nonnegative integer.
    Question 6: Proving a formula by induction

    Use mathematical induction to show that,

    −1, for all non-negative integers n .


    2 n n +1
    1+2+2 + ⋯ + 2 =2

    Question 7: Proving a summation formula by induction

    Prove the following formula by induction:


    2 2
    1+2+2 + ⋯ + 2 n−1=n

    Question 8: Proving a formula by induction

    n
    Prove that 23 −1 is divisible by 11 for all positive integers n .

    Question 9: Proving a summation formula by induction

    Show that the following proposition, P ( n ) is true for all n ≥ 0 by mathematical


    induction.
    n −1

    ∑ 2i =2n−1
    i=0

    You might also like