Chapter 2: Mathematicai Preiiminaries ~ 65
EXAMPLE 2.33
Prove Property 5 stated in Section 2.2.2.
Solution
We prove the result by induction on n. Obviously, there is basis for induction.
Assume the result for connected graphs with n - 1 vertices. Let T be a
connected graph with II vertices and J1 - 1 edges. By Example 2.32, T has at
least one leaf v (say).
Drop the vertex '.' and the (single) edge incident \vith v. The resulting graph
Of is still connected and has 11 - 1 vertices and n
2 edges. By induction
hypothesis. Of is a tree. So 0' has no circuits and hence 0 also has no circuits.
(Addition of the edge incident with v does not create a circuit in G.) Hence G
is a tree. By the principle of induction, the property is true for all n.
EXAMPLE 2.34
A person climbs a staircase by climbing either (i) two steps in a single stride
or (ii) only one step in a single stride. Find a fonnula for Sen), where Sen)
denotes the number of ways of climbing n stairs.
Solution
When there is a single stair. there is only one way of climbing up. Hence
S(l) = 1. For climbing two stairs, there are t\'iO ways. viz. two steps in a single
stride or two single steps. So 5(2) :::: 2. In reaching n steps, the person can climb
either one step or two steps in his last stride. For these two choices, the number
of 'ways are sen - 1) and Sen - 2).
So,
Sen) :::: Sen - 1) + Sen - 2)
Thus. Sen) = F(n). the nth Fibonacci number (refer to Exercise 2.20.
at the end of this chapter).
EXAMPLE 2.35
How many subsets does the set {I, 2, .... n} have that contain no two
consecutive integers?
Solution
Let Sn denote the number of subsets of (1. 2, ... , n} having the desired
property. If n = 1. S] = I{ 0, {lr = 2. If 11 = 2, then S~ = i{ 0, {l}. {2}! :::: 3.
Consider a set A with n elements. If a subset having the desired property
'ontains n, it cannot contain n - 1. So there are Sn-~ suchmbsets. If it does
not contain n. there are Sn-l such subsets. So S" = Sn-J + Sn-~' As S\ = 2 = F 3
and S~ = 3 = Fl,.
the (n + 2)th Fibonacci numbeL
EXAMPLE 2.33
Prove Property 5 stated in Section 2.2.2.
Solution
We prove the result by induction on n. Obviously, there is basis for induction.
Assume the result for connected graphs with n - 1 vertices. Let T be a
connected graph with II vertices and J1 - 1 edges. By Example 2.32, T has at
least one leaf v (say).
Drop the vertex '.' and the (single) edge incident \vith v. The resulting graph
Of is still connected and has 11 - 1 vertices and n
2 edges. By induction
hypothesis. Of is a tree. So 0' has no circuits and hence 0 also has no circuits.
(Addition of the edge incident with v does not create a circuit in G.) Hence G
is a tree. By the principle of induction, the property is true for all n.
EXAMPLE 2.34
A person climbs a staircase by climbing either (i) two steps in a single stride
or (ii) only one step in a single stride. Find a fonnula for Sen), where Sen)
denotes the number of ways of climbing n stairs.
Solution
When there is a single stair. there is only one way of climbing up. Hence
S(l) = 1. For climbing two stairs, there are t\'iO ways. viz. two steps in a single
stride or two single steps. So 5(2) :::: 2. In reaching n steps, the person can climb
either one step or two steps in his last stride. For these two choices, the number
of 'ways are sen - 1) and Sen - 2).
So,
Sen) :::: Sen - 1) + Sen - 2)
Thus. Sen) = F(n). the nth Fibonacci number (refer to Exercise 2.20.
at the end of this chapter).
EXAMPLE 2.35
How many subsets does the set {I, 2, .... n} have that contain no two
consecutive integers?
Solution
Let Sn denote the number of subsets of (1. 2, ... , n} having the desired
property. If n = 1. S] = I{ 0, {lr = 2. If 11 = 2, then S~ = i{ 0, {l}. {2}! :::: 3.
Consider a set A with n elements. If a subset having the desired property
'ontains n, it cannot contain n - 1. So there are Sn-~ suchmbsets. If it does
not contain n. there are Sn-l such subsets. So S" = Sn-J + Sn-~' As S\ = 2 = F 3
and S~ = 3 = Fl,.
the (n + 2)th Fibonacci numbeL