Discrete Structures · Unit 4 · 5 hrs
Induction and Recursion
Exam-focused notes for Induction and Recursion (Discrete Structures, CSC165): what the TU syllabus asks and how it has actually been tested, with 9 solved past questions from this unit.
What this unit covers
- Induction
- mathematical Induction
- Strong Induction and Well Ordering
- Induction in General
- Recursive Definitions and Structural Induction
- Recursive Algorithms
- Proving Correctness of Recursive Algorithms
mathematical Induction
Using mathematical induction show that $5 + 2 + 5 + 8 + ... + (3n-1) = \frac{n(3n+1)}{2}$ [5]
$$5 + 2 + 5 + 8 + \cdots + (3n - 1) = \frac{n(3n+1)}{2}$$ Note: The series begins with the term for $n=1$: when $n=1$, $3(1)-1 = 2$. The leading "5" in the problem statement appears to be a typographical artifact. The series is $2, 5, 8, \ldots, (3n-1)$, wh...
Full solved answer →A group of 8 scientist is composed of 5 chemist and 3 biologist. In how many ways can a committee of 5 be formed that has 3 chemist and 2 biologist? Using mathematical induction prove that $1^3 + 2^3 + 3^3 + ... + n^3 = (n^2(n+1)^2/4)$ for $n \geq 1$. [10]
- Total scientists = 8 (5 chemists + 3 biologists) - Committee required = 5 members: exactly 3 chemists and 2 biologists Select 3 chemists from 5: $$C(5,3) = \frac{5!}{3!\,2!} = \frac{5\times 4}{2\times 1} = 10$$ Select 2 biologists from 3: $$C(3,2) = \frac...
Full solved answer →Prove that for all integers x and y, if $x^2 + y^2$ is even then x + y is even. Using induction prove that $1^3 + 2^3 + 3^3 + ... + n^3 = n^2(n + 1)^2/4$ [10]
The contrapositive of "if x² + y² is even, then x + y is even" is: If x + y is odd, then x² + y² is odd. We prove the contrapositive. This is a valid approach because a statement and its contrapositive are logically equivalent. --- Assume x + y is odd. For ...
Full solved answer →Prove that for every positive integer n≥1,n2+nn \geq 1, n^2 + nn≥1,n2+n is even integer using mathematical induction. [5]
An integer is even if it can be written in the form 2k for some integer k. Also note that: $$n^2 + n = n(n+1)$$ This is the product of two consecutive integers, which will be useful in each step. --- Substitute n = 1: $$n^2 + n = (1)^2 + (1) = 1 + 1 = 2$$ S...
Full solved answer →Prove that $5^n - 1$ is divisible by 4 using mathematical induction. [5]
We want to prove that 4 (5ⁿ - 1) for all positive integers n, i.e., (5ⁿ - 1) is divisible by 4. --- Substitute n = 1: $$5^1 - 1 = 5 - 1 = 4$$ Since 4 is divisible by 4, the base case holds. --- Assume the statement is true for n = k, i.e., assume: $$5^k - 1...
Full solved answer →How can you use mathematical induction to prove statements? Use mathematical induction to show that sum of first n positive integer is $\frac{n(n+1)}{2}$ [10]
Mathematical induction is a proof technique used to prove that a statement P(n) is true for all positive integers n. It works in two steps: Step 1: Basis Step (Base Case) Show that the statement P(1) is true (i.e., verify the statement holds for the smalles...
Full solved answer →Proving Correctness of Recursive Algorithms
Define subset and power set. How do you prove correctness of recursive algorithm using Induction? Illustrate with an example. [5]
--- A set A is called a subset of set B if every element of A is also an element of B. This is denoted as: A ⊆ B if and only if ∀x (x ∈ A → x ∈ B) Example: If A = {a, b} and B = {a, b, c}, then A ⊆ B. - The empty set (∅) is a subset of every set. - Every se...
Full solved answer →Compute the values. 3 mod 4 , 7 mod 5, -5 mod 3 , 11 mod 5 and -8 mod 6Write down the recursive algorithm to find the value of bnb^nbn and prove its correctness using induction.[5+5]
(a) Computing Modular Values For an integer $a$ and positive integer $d$, we write $a \bmod d = r$ where $$a = d \cdot q + r, \qquad 0 \le r < d.$$ The remainder $r$ must be non-negative and strictly less than $d$, so for negative $a$ we take $q = \lfloor a...
Full solved answer →Strong Induction and Well Ordering
Explain strong induction in detail. What is recursively defined function? Use mathematical induction to prove $7^{n+2} + 8^{2n+1}$ is divisible by 57.[10]
--- Strong Induction (also called the Second Principle of Mathematical Induction or Complete Induction) is a variant of mathematical induction where, to prove that a statement P(n) is true for all positive integers n, we assume that P(k) is true for ALL val...
Full solved answer →Make Unit 4 stick
Practice CSC165 with flashcards & quizzes