COMP 3270 β Intro to AlgorithmsHomework 1: Induction practice
Due 08/30/24
50 points
1. Find a counterexample to show that for any
positive integers a and b, π! is not always greater
than ππ π₯ (π, π).
2. Use induction to prove that if π” is a sequence
such that π# = 0 πππ π” = 2π”$% + 2″ for π > 0,
then π” = π2″ for all π β₯ 0.
3. Number of Handshakes in a Meeting
Scenario: In a meeting with π people, each person
shakes hands with every other person exactly
once. You want to ο¬nd the total number of
handshakes.
Claim: The total number of handshakes in a
meeting with n people is given by:
π(π β 1)
π» (π) =
2
4. Prove by induction that for π β₯ 1,
”
π. 5 3π & β 3π + 1 = π)
‘(%
π(3π β 1)
π. 1 + 4 + 7 + β― + (3π β 2) =
2
5. Restaurant table reservation system.
Problem statement: IneWicient reservation
management in a restaurant leads to double
bookings, unbalanced table occupancy, and
customer dissatisfaction.
Problem-Solving Approach: Deο¬ne the problem,
Analyze the requirements, identify patterns,
design algorithm.
Discuss all the steps by giving the steps as
discussed in class. βWriting program is not
required.β