Notion of Induction and Recursion in Mathematics and Computer Science

Explain the relationship between the notion of induction in mathematics and the notion of recursion in computer science

Introduction:

In order to explain the relationship between the notion of induction in mathematics and the notion of recursion in computer science we must look at the similarities and differences between them. The aim of this report is to elaborate on the connection between induction and recursion through providing thorough explanations and examples to support this.

By the end of this report you should be have formed a deeper understanding of both mathematical induction and recursion through comprehending how to develop and create the outlines and formulas.

Body paragraphs:

Induction in mathematics and recursion in computer science are closely related and very much the same thing. Recursion involves using induction to prove that your algorithm is correct, Induction and recursion resemble each other as you need to use one in order to solve the other one. However, there are some differences to each which will be explained below as we look at mathematical induction vs recursion. When you are writing a function, you are trying to prove that, given a natural number, your program will terminate and produce another natural number. Now we may have a definition like this:

f 0 = 1

f (1 + n) = n * f n

which is both a recursive definition of f and an inductive proof of its termination at the same time

Recursion is not limited to a function decreasing its counter, induction also isn’t limited to natural numbers. There is structural induction, corresponding to structural recursion, both of which are very popular in mathematics and programming. These are to use when trying to prove things as well as define functions on more complex data structures.

A technique that can be applied to prove the universal statements for sets of positive integers or their associated sequences is called mathematical induction. Mathematical induction is a technique for showing that a statement P(n) is true for natural numbers n, or for some infinite subset of the natural numbers (e.g. all positive even integers). It is generally used to establish that a given statement, involving integers, is true for all integers starting from an initial number. It is used to prove statements of the form x P(x) where x  Z+.

Get Help With Your Essay

If you need assistance with writing your essay, our professional essay writing service is here to help!
Find out more about our Essay Writing Service

Mathematical induction proofs consist of the following outlines: claim, proof, base and induction. Outline 1 is the claim, where P(n) is true for all positive integers. The 2^nd outline is proof, which is what we’ll use for the induction on n. Outline 3 is the basis, where we verify that the proposition P(n₀) is true. For example, verifying the statement P(n₀) is true for the first value of n, e.g. n = n₀. Lastly, outline 4 is the inductive step in which the implication P(n)  P(n+1), is true for all positive n. Using this presumption, we must prove that P(n+1) is true. Therefore, we conclude x P(x). It is very helpful when starting out on learning mathematical induction is to label your steps in order to see exactly what to do and when.

To be able to prove the implication of a certain type, we need to choose a method of proof first (direct, indirect or contradiction). Direct proof is where we have the ability to use rules to prove the answer is true. For example:

Consider two even integers x and y which can be written as: x = 3a, y = 3b.

The sum can therefore be written as:

x + y = 3a + 3b

= 3(a + b) = 3c

= 3c, where c = a + b

Indirect proof involves proving the solution in a different way through displaying that the opposite can’t be proved. For example: prove this following statement is true by contradiction: If x = 3 then 3x – 5 ≠ 10.

The first thing you do in an indirect proof is assume the conclusion of the statement is false. In this case, we will assume the opposite of if x = 2, then 3x – 5 ≠ 10

Take this statement as true and solve for x.

3x – 5 = 10

3x = 15

x = 5

x = 5 contradicts the given statement that x = 2. Therefore, our assumption is false and 3x – 5 ≠ 10 is true.

Lastly, proof by contradiction uses a negation and can be used in cases other than implications. For example: using proof by contradiction, display that if n is an integer and n² + 1 is odd, then n must be even is true.

First, we assume that n is odd (the conclusion) and that n² + 1 is odd. But if n is odd, then n² is odd, and therefore n² + 1 is even. Thus, showing a contradiction with our assumption.

Here is another example of mathematical induction with explanation of each step…

Claim: P (n) is true for all positive integers (n)

Proof: we’ll use induction on n

Base: we need to show that P (1) is true

Induction: suppose that P (k) is true, for some positive integer k. We need to demonstrate that P (k + 1) is true

Formula: for this formula example, our proposition P (n) is

By substituting in the definition of P, we get the following…

Proof: we will show that  for any positive integer n, using induction on n

Base: we need to demonstrate that the formula holds for n = 1, e.g.

Induction: suppose that for some positive integer k. We need to show

that

The summation notation =

Through substituting this into the formula from our hypothesis we end up with:

After combining these equations we are left with:

Now we’re going to look at the process of recursion and how it interrelates with induction, as well as how it works on its own. The process of recursion is the possibility to define an object (function, sequence, algorithm, structure) in terms of itself. Recursion involves solving a large problem by splitting it into smaller problems of the same kind. Recursion should be used if a problem is too large and you are able to determine small values, or if there is a clear connection between small and large cases.

There are various steps involved in the problem solving of recursion. Step 1 involves creating and analysing the smaller issues of the problem. The 2^nd step includes trying to construct larger cases through using smaller cases. Step 3 encompasses making an educated guess about small cases being related to the largest case as a whole. The 4^th step is proving your guess and interpreting it into a formula that uses the answers of the smaller cases in order to find the final answer of the larger case. The final step is using your formula to develop the solution to the distinct layer you care about.

The process of recursion may seem difficult but it can easily be simplified to thinking about climbing a ladder. To move up to each step on the ladder you must depend on stepping onto the step below it. Therefore, you must work your way up the ladder through certain steps, just like working through steps in a mathematical equation to continue moving forward.

Here is a simple example of how to create a recursive formula:

Sequence: {3, 6, 12, 24, 48, 96, …}

Subscript notation: a₁ = 3; a_n = 2 a_n – 1

Function notation: f (1) = 3; f (n) = 2 f (n – 1)

To create a recursive formula, the common ratio is usually easily seen and used. For example:

Here is another example of assuming a recursive function on positive integers…

F (0) = 3

F (n + 1) = 2f (n) + 3 

What is the value of f (0) ? 3

-          f (1) = 2f (0) + 3 = 2 (3) + 3 = 6 + 3 = 9

-          f (2) = f (1 + 1) = 2f (1) + 3 = 2 (9) + 3 = 18 + 3 = 21

-          f (3) = f (2 + 1) = 2f (2) + 3 = 2 (21) = 42 + 3 = 45

-          f (4) = f (3 + 1) = 2f (3) + 3 = 2 (45) + 3 = 90 + 3 = 93

Conclusion:

Overall, we can see the interrelationships between the notion of induction in mathematics and the notion of recursion in computer science. In this report we have looked at the outlines of how to work out mathematical induction through using claim, proof, base and induction. We have also looked at how to shape the formula of recursion, through breaking down the larger issue into smaller cases, reconstructing them and developing a formula to work out the solution. Hopefully by now you’ve gained a deeper understanding of the relationship between the induction of mathematics and notion of recursion in computer science.

REFERENCES:

• Leron U. & Zazkis R. 2010, Computational recursion and mathematical induction, FLM Publishing Association, retrieved 14 May 2019, <http://www.sfu.ca/sfublogs-archive/people/zazkis/uploads/2010/05/Induction-and-Recursion.pdf>
• ‘Computational recursion and mathematical induction’ (2010)
• 2015, CS 160 Foundations in Programming, Colorado State University, retrieved 14 May 2019, <https://www.cs.colostate.edu/~cs160/.Spring15/tutorials/tut_4.php>