IGNOU MTE-13 Solved Question Paper PDF Download

IGNOU MTE-13 Previous Year Solved Question Paper in Hindi

IGNOU MTE-13 Previous Year Solved Question Paper in English

Q1. Which of the following statements are True and which are False? Justify your answers: (i) There is at least one graph with five vertices of degrees 2, 2, 2, 2, 3. (ii) The generating function for the sequence aₙ = n+1 is 1/(1+z). (iii) q → (p → q) is a tautology. (iv) There is a 3-regular graph on n vertices, ∀n≥4. (v) 5 has a self-conjugate partition.

Ans. (i) False . According to the Handshaking Lemma in graph theory, the sum of the degrees of all vertices in any graph is equal to twice the number of edges, which must be an even number. For the given degrees, the sum is 2 + 2 + 2 + 2 + 3 = 11. Since the sum (11) is an odd number, no such graph can exist.

(ii) False . For the sequence aₙ = n+1, the terms are 1, 2, 3, 4, … . The generating function is G(z) = Σ(n+1)zⁿ = 1 + 2z + 3z² + … . We know that the Maclaurin series expansion of 1/(1-z)² is Σ(n+1)zⁿ. The given function is 1/(1+z), which expands to 1 – z + z² – z³ + …, generating the sequence 1, -1, 1, -1, … . Therefore, the given statement is false.

(iii) True . To prove a statement is a tautology, we must show it is true for all possible truth values of p and q. We can check this in two cases:

• Case 1: If q is True (T). Then (p → q) will also be True (T), as anything implies T. The entire statement q → (p → q) becomes T → T, which is T.
• Case 2: If q is False (F). Then the entire statement becomes F → (p → F). An implication with a false antecedent is always true. Thus, the statement is True (T).

Since the statement is true in both cases, it is a tautology.

(iv) False . In a k-regular graph on n vertices, the sum of degrees is k×n. By the Handshaking Lemma, k×n must be even. If k=3, then 3n must be even, which implies that n (the number of vertices) must be even. The statement claims this holds for all n≥4, which includes odd values like n=5. For n=5, the sum of degrees would be 3×5=15, which is odd. Thus, a 3-regular graph on 5 vertices cannot exist. Therefore, the statement is false.

(v) True . A partition of a number is self-conjugate if its Ferrers graph is symmetric about the main diagonal. Consider the partition of 5 as 3 + 1 + 1 . The Ferrers graph is: * * * The conjugate of this graph is obtained by reading the columns as rows. The first column has 3 dots, the second has 1, and the third has 1. This gives the partition 3 + 1 + 1. Since the partition is equal to its conjugate, it is a self-conjugate partition.

Q2. (a) Using induction, show that: 2n² > (n+1)², ∀n>3 (b) Find the general solution of the recurrence relation: aₙ − 3aₙ₋₁ = 3.2ⁿ. Also find the solution when a₁ = 6. (c) Prove or disprove: “The complete graph, K₅, has a Eulerian circuit.”

Ans. (a) We will prove 2n² > (n+1)² for all n > 3 by mathematical induction. Base Case: For n = 4 (the first integer for n>3). LHS = 2(4)² = 2(16) = 32. RHS = (4+1)² = 5² = 25. Since 32 > 25, the statement holds for n=4. Inductive Hypothesis: Assume the statement is true for some integer k > 3. That is, 2k² > (k+1)². Inductive Step: We need to prove the statement for n = k+1. That is, 2(k+1)² > ((k+1)+1)² = (k+2)². Starting with the LHS: 2(k+1)² = 2(k² + 2k + 1) = 2k² + 4k + 2. From the inductive hypothesis, we know 2k² > (k+1)². Substituting this in: 2k² + 4k + 2 > (k+1)² + 4k + 2 = (k² + 2k + 1) + 4k + 2 = k² + 6k + 3. Now we need to show that k² + 6k + 3 > (k+2)². (k+2)² = k² + 4k + 4. So we must prove: k² + 6k + 3 > k² + 4k + 4 ⇒ 2k > 1 ⇒ k > 1/2. Since our hypothesis is for k > 3, which certainly satisfies k > 1/2, the inequality is true. Thus, 2(k+1)² > (k+2)². By induction, the statement is true for all integers n > 3.

(b) The given recurrence relation is: aₙ − 3aₙ₋₁ = 3.2ⁿ. 1. Homogeneous Solution: The homogeneous equation is aₙ − 3aₙ₋₁ = 0. The characteristic equation is r – 3 = 0, which has the root r=3. So, the homogeneous solution is aₙ⁽ʰ⁾ = A(3)ⁿ.

2. Particular Solution: Since the RHS is 3.2ⁿ, we assume a particular solution of the form aₙ⁽ᵖ⁾ = C(2)ⁿ. Substituting this into the relation: C(2)ⁿ – 3(C(2)ⁿ⁻¹) = 3.2ⁿ C(2)ⁿ – (3/2)C(2)ⁿ = 3.2ⁿ (C – 3C/2)(2)ⁿ = 3(2)ⁿ -C/2 = 3 ⇒ C = -6. So, the particular solution is aₙ⁽ᵖ⁾ = -6(2)ⁿ.

3. General Solution: The general solution is the sum of the homogeneous and particular solutions: aₙ = aₙ⁽ʰ⁾ + aₙ⁽ᵖ⁾ = A(3)ⁿ – 6(2)ⁿ.

Now, we use the condition a₁ = 6 to find A: a₁ = A(3)¹ – 6(2)¹ = 6 3A – 12 = 6 3A = 18 A = 6.

Therefore, the specific solution with the given initial condition is: aₙ = 6(3)ⁿ – 6(2)ⁿ .

(c) Prove . A graph has an Eulerian circuit if and only if it is connected and every vertex has an even degree. The complete graph K₅ is a graph with 5 vertices, where every vertex is connected to every other vertex. 1. Connectivity: K₅ is connected because every vertex is directly connected to every other vertex. 2. Vertex Degrees: In K₅, the degree of each vertex is n-1, where n is the number of vertices. Here n=5, so the degree of each vertex is 5-1 = 4. Since the number 4 is an even number, all 5 vertices of K₅ have an even degree. Since K₅ is connected and all its vertices have even degree, it has an Eulerian circuit. Therefore, the statement is true.

Q3. (a) Define a complete matching in a bipartite graph. Check whether or not, there is a complete matching in the following graph. (b) Calculate the Stirling number S(5, 4). (c) Using the generating function technique, evaluate the sum: Σ k 2ᵏ C(n, k) for k=1 to n.

Ans. (a) Definition of a Complete Matching: In a bipartite graph G = (U ∪ V, E), where U and V are the two disjoint sets of vertices, a matching is a subset of edges M ⊆ E such that no two edges in M share a common vertex. A matching is called a complete matching from U to V if it saturates every vertex in U, i.e., every vertex in U is an endpoint of some edge in M. This requires that |U| ≤ |V|. If |U| = |V|, it is often called a perfect matching.

Checking the given graph: The given graph is bipartite with partitions X = {A, B, C, D} and Y = {a, b, c, d}. Here, |X| = |Y| = 4. We need to check if a complete matching from X to Y exists. We can try to construct one that covers all vertices of X. Consider the potential matching M: M = {(A, a), (B, b), (C, c), (D, d)} Let’s check if this is a valid matching:

• The edge (A, a) exists in the graph.
• The edge (B, b) exists in the graph.
• The edge (C, c) exists in the graph.
• The edge (D, d) exists in the graph.

None of these four edges share a common vertex. This matching M covers all vertices {A, B, C, D} in set X.

Therefore,

yes, a complete matching exists in the given graph

.

(b) Stirling Number S(5, 4): The Stirling number of the second kind, denoted S(n, k) or {n k}, is the number of ways to partition a set of n elements into k non-empty disjoint subsets. We need to calculate S(5, 4), which is the number of ways to partition a set of 5 elements (say {1, 2, 3, 4, 5}) into 4 non-empty subsets. To partition 5 elements into 4 subsets, the only possible form of the partition is to have one subset of size 2, and the remaining three subsets of size 1 each. For example: {{1, 2}, {3}, {4}, {5}}. The task, therefore, is simply to find the number of ways to choose the 2 elements that will be in the same subset. The number of ways to choose 2 elements from 5 is given by the combination C(5, 2). C(5, 2) = 5! / (2! * (5-2)!) = (5 × 4) / (2 × 1) = 10. Thus, S(5, 4) = 10 .

(c) We will use the generating function technique to evaluate the sum S = Σ k 2ᵏ C(n, k) from k=1 to n. We start with the Binomial Theorem: (1 + x)ⁿ = Σ C(n, k) xᵏ (from k=0 to n)

Now, we differentiate this equation with respect to x: d/dx [(1 + x)ⁿ] = d/dx [Σ C(n, k) xᵏ] n(1 + x)ⁿ⁻¹ = Σ C(n, k) k xᵏ⁻¹ (from k=1 to n) (The k=0 term is a constant, so its derivative is 0)

Now, we manipulate the equation to match the given sum. We multiply both sides of the equation by x: n x (1 + x)ⁿ⁻¹ = Σ C(n, k) k xᵏ (from k=1 to n)

This is almost the desired sum, except we have 2ᵏ instead of xᵏ. This indicates that we should substitute x=2. Setting x = 2: n 2 (1 + 2)ⁿ⁻¹ = Σ C(n, k) k 2ᵏ (from k=1 to n) 2n (3)ⁿ⁻¹ = S

Thus, the value of the sum is 2n * 3ⁿ⁻¹ .

Q4. (a) Test the validity of the following argument using truth table: p→q, r∨~q, r ∴ ~p (b) Let G be a graph with n vertices. Prove that if G is a tree, then G is acyclic and has n-1 edges.

Ans. (a) An argument is valid if and only if every time all the premises are true, the conclusion is also true. Premises: P1: p→q, P2: r∨~q, P3: r Conclusion: C: ~p

We will construct a truth table to check the validity of the argument. We need to find the rows where P1, P2, and P3 are all True (T), and then check the truth value of C in those rows.

| p | q | r | ~q | p→q (P1) | r∨~q (P2) | r (P3) | ~p (C) | |—|—|—|—|—|—|—|—| | T | T | T | F | T | T | T | F | | T | T | F | F | T | F | F | F | | T | F | T | T | F | T | T | F | | T | F | F | T | F | T | F | F | | F | T | T | F | T | T | T | T | | F | T | F | F | T | F | F | T | | F | F | T | T | T | T | T | T | | F | F | F | T | T | T | F | T |

Now, we identify the rows where all premises P1, P2, and P3 are true. These are:

• Row 1: p=T, q=T, r=T. Here P1, P2, P3 are all T. In this row, the conclusion C (~p) is F (False).
• Row 5: p=F, q=T, r=T. Here P1, P2, P3 are all T. In this row, the conclusion C (~p) is T (True).
• Row 7: p=F, q=F, r=T. Here P1, P2, P3 are all T. In this row, the conclusion C (~p) is T (True).

Since there exists a case (Row 1: p=T, q=T, r=T) where all the premises are true but the conclusion is false, the argument is

invalid

.

(b) We need to prove that if G is a tree, then (1) G is acyclic and (2) G has n-1 edges.

1. Acyclicity: By the very definition of a tree, it is a connected acyclic graph . Therefore, if G is a tree, it is acyclic by definition.

2. Number of Edges: We will prove this by induction on n, the number of vertices. Base Case: For n=1. A tree with one vertex has no edges. The number of edges = 0, and n-1 = 1-1 = 0. So it holds for n=1.

Inductive Hypothesis: Assume that for any tree with k vertices, where k < n, it has k-1 edges.

Inductive Step: Let G be a tree with n vertices (where n > 1). A property of any tree (with n>1) is that it has at least one vertex of degree 1 (called a leaf). If not, all vertices would have degree ≥ 2, and a walk in the graph would eventually lead to a cycle, which contradicts the definition of a tree. Let v be a leaf in G, and let e be the edge incident to v. Consider a new graph G’ = G – {v}, obtained by removing v and the edge e.

• G’ has n-1 vertices.
• G’ is connected, because removing a leaf from a connected graph (with n>1) does not disconnect it.
• G’ is acyclic, because removing a vertex and an edge cannot create a cycle.

Therefore, G’ is also a tree on n-1 vertices.

By the inductive hypothesis, G’ must have (n-1)-1 = n-2 edges.

The original graph G can be obtained by adding the vertex v and the edge e back to G’.

Therefore, the number of edges in G = (Number of edges in G’) + 1 = (n-2) + 1 =

n-1

.

Thus, by induction, it is proved that any tree with n vertices has n-1 edges.

Q5. (a) A box contains 7 blue and 5 black balls. 4 balls are selected from the box at random. What is the probability that 2 of the selected balls will be black and 2 will be blue. (b) If Kₘ,ₙ for m, n ≥ 2, is Hamiltonian, how are m and n related? Justify your answer. (c) Find the solution of the recurrence relation: aₙ = 3aₙ₋₁ + 4aₙ₋₂; a₀=0, a₁=5.

Ans. (a) Problem Analysis: Total balls = 7 blue + 5 black = 12 balls. Number of balls to be selected = 4. We need to find the probability of selecting 2 black and 2 blue balls.

1. Total Possible Outcomes: The total number of ways to select 4 balls from 12 is given by the combination C(12, 4). C(12, 4) = 12! / (4! * (12-4)!) = (12 × 11 × 10 × 9) / (4 × 3 × 2 × 1) = 495.

2. Favorable Outcomes: We need to select 2 black and 2 blue balls. The number of ways to select 2 black balls from 5 is C(5, 2). C(5, 2) = 5! / (2! * 3!) = (5 × 4) / 2 = 10. The number of ways to select 2 blue balls from 7 is C(7, 2). C(7, 2) = 7! / (2! * 5!) = (7 × 6) / 2 = 21. By the rule of product, the total ways to choose 2 black and 2 blue balls = C(5, 2) × C(7, 2) = 10 × 21 = 210.

3. Probability Calculation: Probability = (Number of Favorable Outcomes) / (Total Possible Outcomes) P(2 black and 2 blue) = 210 / 495 Simplifying this fraction (by dividing both numerator and denominator by 15): 210 ÷ 15 = 14 495 ÷ 15 = 33 Thus, the probability is 14/33 .

(b) If the complete bipartite graph Kₘ,ₙ is Hamiltonian, then m and n must be equal (m = n) .

Justification: A Hamiltonian cycle is a cycle that visits every vertex of the graph exactly once. Let the two partitions of Kₘ,ₙ be X and Y, where |X|=m and |Y|=n. Any path or cycle in Kₘ,ₙ must alternate between vertices from X and Y (e.g., x₁ → y₁ → x₂ → y₂ …). A Hamiltonian cycle must contain all m+n vertices. Since the cycle alternates between X and Y, starting from a vertex in X, the cycle must contain an equal number of vertices from X and Y to be able to return to the starting vertex. For example, if the cycle starts at x₁, the path looks like x₁, y₁, x₂, y₂, …, xₖ, yₖ. To complete the cycle, yₖ must connect back to x₁. This implies the path contains k vertices from X and k vertices from Y. Since the Hamiltonian cycle must cover all vertices, it will have m vertices from X and n vertices from Y. Due to the alternating nature, this is only possible if m = n .

Furthermore, a corollary of Dirac’s theorem states that if a bipartite graph G=(X∪Y, E) has |X|=|Y|=n ≥ 2, and every vertex has degree greater than n/2, then G is Hamiltonian. In Kₙ,ₙ, every vertex has degree n, which is greater than n/2 (for n≥2), so Kₘ,ₙ is always Hamiltonian for m=n≥2.

(c) The given linear homogeneous recurrence relation is: aₙ = 3aₙ₋₁ + 4aₙ₋₂. 1. Characteristic Equation: We form the characteristic equation by assuming a solution of the form aₙ = rⁿ: rⁿ = 3rⁿ⁻¹ + 4rⁿ⁻² r² = 3r + 4 r² – 3r – 4 = 0

2. Finding the Roots: We solve this quadratic equation by factoring: r² – 4r + r – 4 = 0 r(r – 4) + 1(r – 4) = 0 (r – 4)(r + 1) = 0 The roots are r₁ = 4 and r₂ = -1.

3. General Solution: Since the roots are distinct, the general solution is of the form: aₙ = A(r₁)ⁿ + B(r₂)ⁿ = A(4)ⁿ + B(-1)ⁿ

4. Using Initial Conditions to Find Constants: We are given a₀ = 0 and a₁ = 5. For n = 0: a₀ = A(4)⁰ + B(-1)⁰ = A + B 0 = A + B ⇒ B = -A (Equation 1)

For n = 1: a₁ = A(4)¹ + B(-1)¹ = 4A – B 5 = 4A – B (Equation 2)

Now substitute B = -A from Equation 1 into Equation 2: 5 = 4A – (-A) 5 = 5A A = 1

Substituting A=1 into Equation 1, we get B = -1.

5. Final Solution: Placing the values of A=1 and B=-1 into the general solution, we get the final solution: aₙ = 1(4)ⁿ – 1(-1)ⁿ = 4ⁿ – (-1)ⁿ

Q6. (a) If a k-regular graph has no cycle of length less than five, show that it must have at least k² + 1 vertices. (b) Without using a truth table, find the CNF of the Boolean expression: [(x₁ ∧ x₂) ∨ (x₁’ ∧ x₃’)]’.

Ans. (a) Let G be a k-regular graph with no cycles of length 3 or 4. This means the girth of G is at least 5. We will show that the number of vertices in G must be at least k² + 1.

Pick an arbitrary vertex v .

• Since the graph is k-regular, v has exactly k neighbours. Let’s call the set of these neighbours N(v) = {u₁, u₂, …, uₖ}. These vertices are at distance 1 from v.
• Consider any two neighbours of v, say uᵢ and uⱼ (with i ≠ j). If there were an edge between uᵢ and uⱼ, it would form the cycle v-uᵢ-uⱼ-v of length 3. Since the graph has no cycles of length 3, no two neighbours of v are adjacent.
• Now consider the neighbours of any uᵢ ∈ N(v). Since G is k-regular, uᵢ also has k neighbours. One of these neighbours is v itself.
• The other k-1 neighbours of uᵢ cannot be v.
• Furthermore, can any other neighbour of uᵢ (besides v) be equal to another member uⱼ of N(v)? No, because we have already established there are no edges within N(v).
• Now, consider if two distinct neighbours, uᵢ and uⱼ, could share a common neighbour w (other than v). If they did, it would form the cycle v-uᵢ-w-uⱼ-v of length 4. Since the graph has no cycles of length 4, this is not possible.

This implies that the k-1 neighbours of each uᵢ (other than v) must be distinct from v, from all other members of N(v), and from the non-v neighbours of all other members of N(v).

Let’s count the vertices: 1. The starting vertex: v (1 vertex) 2. The neighbours of v (vertices at distance 1): {u₁, u₂, …, uₖ} (k vertices) 3. The neighbours of the neighbours of v, excluding v (vertices at distance 2): Each uᵢ has k-1 unique neighbours. Since all these are unique, there are a total of k × (k-1) such vertices.

All these vertices must be distinct, otherwise, a cycle of length 3 or 4 would be formed. Therefore, the minimum total number of vertices is: Number of vertices ≥ 1 (for v) + k (for neighbours of v) + k(k-1) (for neighbours of neighbours) ≥ 1 + k + k² – k ≥ k² + 1

Thus, the graph must have at least k² + 1 vertices.

(b) We need to find the Conjunctive Normal Form (CNF) of the Boolean expression [(x₁ ∧ x₂) ∨ (x₁’ ∧ x₃’)]’. CNF is a conjunction (AND) of clauses, where each clause is a disjunction (OR) of literals.

Given expression: E = [(x₁ ∧ x₂) ∨ (x₁’ ∧ x₃’)]’

Step 1: Apply De Morgan’s Law to the outermost negation. De Morgan’s Law: (A ∨ B)’ = A’ ∧ B’ Here, let A = (x₁ ∧ x₂) and B = (x₁’ ∧ x₃’). E = (x₁ ∧ x₂)’ ∧ (x₁’ ∧ x₃’)’

Step 2: Apply De Morgan’s Law to the inner negations. De Morgan’s Law: (A ∧ B)’ = A’ ∨ B’ For the first term: (x₁ ∧ x₂)’ = (x₁’ ∨ x₂’) For the second term: (x₁’ ∧ x₃’)’ = (x₁’)’ ∨ (x₃’)’

Step 3: Simplify the double negations. The double negation law is (A’)’ = A. In the second term, (x₁’)’ = x₁ and (x₃’)’ = x₃. So, (x₁’ ∧ x₃’)’ = (x₁ ∨ x₃).

Step 4: Combine the simplified parts. E = (x₁’ ∨ x₂’) ∧ (x₁ ∨ x₃)

The resulting expression, (x₁’ ∨ x₂’) ∧ (x₁ ∨ x₃) , is a conjunction of two clauses, (x₁’ ∨ x₂’) and (x₁ ∨ x₃). Each clause is a disjunction of literals. This fits the definition of CNF.

Therefore, the CNF of the given expression is (x₁’ ∨ x₂’) ∧ (x₁ ∨ x₃) .

Q7. (a) Let S = {xᵢ : 1≤i≤7}. If the members of this set are arranged on a circle, find the number of arrangements, when x₁ and x₆ are always adjacent to each other. (b) A school has 100 students with 40 of them taking English, 40 taking Hindi and 40 taking Punjabi. 20 students are taking English and Hindi, 20 taking Hindi and Punjabi, 20 taking English and Punjabi and 10 taking all three languages. Find out how many students are taking no languages. (c) Let aₙ denote the number of ways of climbing a staircase with n steps such that one step or two steps are taken at a time. Find a recurrence relation for aₙ and initial conditions that would be required for solving it.

Ans. (a) We need to arrange the 7 members of S = {x₁, x₂, x₃, x₄, x₅, x₆, x₇} in a circle, with the condition that x₁ and x₆ are always adjacent.

Step 1: Treat the adjacent members as a single unit. Since x₁ and x₆ must always be together, we can treat them as a single block or unit, {x₁, x₆}.

Step 2: Arrange the units in a circle. Now we have a total of 6 “units” to arrange: {x₁, x₆}, x₂, x₃, x₄, x₅, x₇. The number of ways to arrange n distinct items in a circle is (n-1)!. So, the number of ways to arrange these 6 units in a circle is (6-1)! = 5!. 5! = 5 × 4 × 3 × 2 × 1 = 120.

Step 3: Consider internal arrangements. Within the single block {x₁, x₆}, the two members x₁ and x₆ can switch their positions. They can be arranged as (x₁, x₆) or (x₆, x₁). The number of these internal arrangements is 2! = 2.

Step 4: Calculate the total arrangements. The total number of arrangements is the product of the number of circular arrangements of the units and the number of internal arrangements. Total arrangements = (5!) × (2!) = 120 × 2 = 240 . Thus, there are 240 arrangements where x₁ and x₆ are always adjacent.

(b) We will use the Principle of Inclusion-Exclusion to solve this problem. Total students = 100. Let: E = set of students taking English, |E| = 40 H = set of students taking Hindi, |H| = 40 P = set of students taking Punjabi, |P| = 40 |E ∩ H| = 20 (both English and Hindi) |H ∩ P| = 20 (both Hindi and Punjabi) |E ∩ P| = 20 (both English and Punjabi) |E ∩ H ∩ P| = 10 (all three languages) (Note: The English version of the question has a typo stating “0 taking all three languages”. The solution uses the value 10 from the Hindi version, which is more typical for such problems.)

Step 1: Find the number of students taking at least one language. |E ∪ H ∪ P| = |E| + |H| + |P| – (|E ∩ H| + |H ∩ P| + |E ∩ P|) + |E ∩ H ∩ P| |E ∪ H ∪ P| = (40 + 40 + 40) – (20 + 20 + 20) + 10 |E ∪ H ∪ P| = 120 – 60 + 10 |E ∪ H ∪ P| = 70. So, 70 students take at least one language.

Step 2: Find the number of students taking no language. This can be found by subtracting the number of students taking at least one language from the total number of students. Students taking no language = (Total students) – |E ∪ H ∪ P| = 100 – 70 = 30. Therefore, 30 students are taking no languages.

(c) Let aₙ be the number of ways to climb n steps, taking either one or two steps at a time.

Recurrence Relation: To reach the n-th step, the final move must have been made from either step (n-1) or step (n-2).

• Case 1: The last move was a single step from step (n-1). The number of ways to have reached step (n-1) is aₙ₋₁.
• Case 2: The last move was a double step from step (n-2). The number of ways to have reached step (n-2) is aₙ₋₂.

Since these two cases are mutually exclusive, the total number of ways to reach step n is the sum of the ways for these two cases.

Therefore, the recurrence relation is:

aₙ = aₙ₋₁ + aₙ₋₂

, for n ≥ 2.

This is the famous Fibonacci relation.

Initial Conditions: To solve this relation, we need two initial values.

• a₁ (Ways to climb 1 step): There is only one way: take a single 1-step. So, a₁ = 1 .
• a₂ (Ways to climb 2 steps): There are two ways: (1) take two 1-steps, or (2) take a single 2-step. So, a₂ = 2 .

These two initial conditions, a₁ = 1 and a₂ = 2, are sufficient for solving the recurrence relation.

(Alternatively, one could define a₀ = 1, representing one way to climb 0 stairs – by doing nothing. Then a₂ = a₁ + a₀ = 1+1=2, which is consistent.)