Scribd
Upload
11 views1 page

ToolkitProblem Set1

The document is a problem set for a CS Toolkit course authored by Bireswar Das, focusing on mathematical induction and related problems. It includes five specific problems that require proofs or demonstrations using induction, covering topics such as divisibility, handshaking scenarios, factorial growth, Fibonacci sequence properties, and representations of integers as sums of powers of 2. The document encourages students to engage deeply with the problems before seeking solutions online.

Uploaded by

mas237105.iitd
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
11 views1 page

ToolkitProblem Set1

The document is a problem set for a CS Toolkit course authored by Bireswar Das, focusing on mathematical induction and related problems. It includes five specific problems that require proofs or demonstrations using induction, covering topics such as divisibility, handshaking scenarios, factorial growth, Fibonacci sequence properties, and representations of integers as sums of powers of 2. The document encourages students to engage deeply with the problems before seeking solutions online.

Uploaded by

mas237105.iitd
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

CS Toolkit Problem Set Problem Set # 1

Bireswar Das (Aug 2025)

Most likely, you will find solutions to all these problems on the internet. However, the
best way not to learn the subject is to simply look at the solutions. You are strongly
encouraged to spend time on each problem before referring to the solution. It is expected
that you may sometimes spend multiple days on a single problem set.

1 Induction
Problem 1.1. Show that for any integer (11)n+2 + (12)2n+1 is divisible by 133.

Problem 1.2. When n couples arrived at a party, they were greeted by the host and hostess
at the door. After rounds of handshaking, the host asked the guests as well as his wife (the
hostess) to indicate the number of hands each of them had shaken. He got 2n + 1 different
answers. Given that no one shook hands with his or her spouse, how many hands had the
hostess shaken? Prove your result by induction.

Problem 1.3. Let d be a positive integer. Show by induction that n! ≥ dn for large enough
n. Here, one of your tasks is to figure out how large is ‘large enough’, i.e., finding out the
right base case.

Problem 1.4. The Fibonacci sequence is defined as:

F0 = 0, F1 = 1, and for n ≥ 2, Fn = Fn−1 + Fn−2 .


√ √
Let ϕ = 1+2 5 and ϕ̄ = 1−2 5 .
Prove by mathematical induction that for all integers n ≥ 0,

(ϕ)n − (ϕ̄)n
Fn = √ .
5
Problem 1.5. Show that every positive integer n can be written as a sum of distinct non-
negative integer powers of 2.

You might also like