Scribd Logo
Upload

Welcome to Scribd!

  • 19 views

    Wk04 Tutorial Induction Questions

    Uploaded by

    Fred
    This document provides practice problems for a discrete structures tutorial on induction, including: 1) Proving that the sum of the first n odd integers equals n^2 using a basic induction proof. 2) Proving that any number of the form 11n + 4 is divisible by 5 using induction. 3) Proving that any class of 18 or more students can be divided into teams of 4 or 7 people using induction. 4) Using induction to prove an upper bound on the number of recursive calls in a fast power algorithm.

    Copyright:

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

    Wk04 Tutorial Induction Questions

    Uploaded by

    Fred
    19 views2 pages
    This document provides practice problems for a discrete structures tutorial on induction, including: 1) Proving that the sum of the first n odd integers equals n^2 using a basic induction proof. 2) Proving that any number of the form 11n + 4 is divisible by 5 using induction. 3) Proving that any class of 18 or more students can be divided into teams of 4 or 7 people using induction. 4) Using induction to prove an upper bound on the number of recursive calls in a fast power algorithm.

    Original Description:

    Wk04 Tutorial Induction Questions

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    This document provides practice problems for a discrete structures tutorial on induction, including: 1) Proving that the sum of the first n odd integers equals n^2 using a basic induction proof. 2) Proving that any number of the form 11n + 4 is divisible by 5 using induction. 3) Proving that any class of 18 or more students can be divided into teams of 4 or 7 people using induction. 4) Using induction to prove an upper bound on the number of recursive calls in a fast power algorithm.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    19 views2 pages

    Wk04 Tutorial Induction Questions

    Uploaded by

    Fred
    This document provides practice problems for a discrete structures tutorial on induction, including: 1) Proving that the sum of the first n odd integers equals n^2 using a basic induction proof. 2) Proving that any number of the form 11n + 4 is divisible by 5 using induction. 3) Proving that any class of 18 or more students can be divided into teams of 4 or 7 people using induction. 4) Using induction to prove an upper bound on the number of recursive calls in a fast power algorithm.

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 2

    CITS2211 Discrete Structures

    Week 4 Tutorial Induction

    August 17, 2017

    1. Prove that:
    n. 1 + 3 + 5 + + (2n 1) = n2

    (This is an elementary crank the handle or plain vanilla induction proof, so you should
    focus on formatting it as correctly as possible.)

    2. Prove that for any n 1, the value 11n + 4 is divisible by 5.

    3. Prove that any class of 18 or more students can be assembled into teams of size 4 or 7.

    4. Consider the following method for calculating fastPower as discussed in lectures.


    public int fastPower(int base, int exponent) {
    if (exponent == 0)
    return 1
    else if (exponent % 2 == 1) // exponent is odd
    return base fastPower(base, exponent1)
    else // exponent is even
    return fastPower(base base, exponent / 2)
    }

    Suggest an expression for the number of recursive calls required given any input e. You can
    give an upper bound rather than exact expression. Use induction to prove your hypothesis.

    For more practice questions see Chapter 5 of Mathematics for Computer Science

    Challenge Questions
    5. Consider a 2n 2n chessboard, with a single square removed from the top-right corner. Show
    that any such chessboard can be completely covered by L-shaped tiles as shown in the diagram.

    (This is a more interesting induction proof as it is not just a simple statement about integers;
    however it is quite straightforward, and only needs weak induction.)

    1

    6. How far can you generalize the proof of Theorem 1.8.1 (below) that p is irrational? For

    example, how about 3? Can you generalise this with an inductive hypothesis?
    Source: Problem 1.13. Mathematics for Computer Science

    You might also like