Proofs – intro to algrathims

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 find 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: Define 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.”