SIT192 Report: Mathematical Induction and Recursion in CS

This report explores the relationship between mathematical induction and recursion, two fundamental concepts with significant applications in both mathematics and computer science. The report begins with an introduction that explains what is going to be discussed, followed by definitions of induction and recursion. It then delves into the close relationship between mathematical induction and recursion, highlighting how induction is used to prove the validity of recursive procedures and algorithms. The report uses examples to explain how the syntax of recursion in programming closely follows the construction of a mathematical statement. It illustrates how a complex problem can be broken down into smaller, similar subproblems. The report also discusses different types of recursion, such as tail, linear, and binary recursion, and their functionalities in programming. Finally, it concludes by summarizing the key similarities and differences between induction and recursion, emphasizing their interconnectedness and importance for computer science students. The report includes references to external resources for further study.

INDUCTION IN MATHEMATICS AND THE CONCEPT OF RECURSION IN COMPUTER
SCIENCE
1
RELATIONSHIP BETWEEN THE CONCEPT OF INDUCTION IN MATHEMATICS AND
THE CONCEPT OF RECURSION IN COMPUTER SCIENCE
Name of Student:
Name of Institution:
Date:

INDUCTION IN MATHEMATICS AND THE CONCEPT OF RECURSION IN COMPUTER
SCIENCE
2
Introduction
Computer science borrows heavily from the discipline of mathematics. Various topics in
mathematics from the basic operations of addition, subtraction, multiplication, and division, to
other concepts in logic, counting, recursion, probability, and matrices just to mention a few are
fundamental in the design and implementation of algorithms, computer systems and the design of
the software. Generally, the concepts present in discrete mathematics forms the foundation on
which computer science principles and concepts are established (Henderson, n.d). Induction in
mathematics is a method of proof used to justify that particular mathematical statements hold for
some positive integer (n). Recursion is basically defining something using entities of its type or
rather just defining it by itself. In computer science, Recursion provides a solution to a problem
by considering the smaller scenarios of the problem with the same nature.
Recursion and Induction
Recursion and induction are closely related as concepts, even without considering their
applications in both mathematics and computer science. In mathematics, induction is mostly
applied on natural numbers but its application is not limited to this scope. Mathematical
induction is built on the premise that;
When a statement holds for a positive integer n=k, then it also holds for n=k+1, this is the
induction hypothesis that is proved by the theorem of induction. If the statement holds for n=1,
then it will be valid for all natural numbers.

INDUCTION IN MATHEMATICS AND THE CONCEPT OF RECURSION IN COMPUTER
SCIENCE
3
For instance:
To show that the sum of the first n positive integers is given by:
1 + 2 + 3 +. . . + n =
n(n + 1)
2
Proof by Induction
First, assume that the formula holds for n = k; that is;
1 + 2 + 3 +. . . + k =
k(k + 1)
2
. ……………………………..(1)
This is the induction assumption. Assuming this, it is imperative to show that the formula holds
for its successor, n = k + 1. That is;
1 + 2 + 3 +. . . + (k + 1) =
(k + 1)(k + 2)
2
………………………(2)
This is done by adding the next term (k + 1) to both sides of the induction assumption from
statement (1). This results in;
1 + 2 + 3 + … + k + (k+1) = k (k+ 1)
2 +( k +1)
= k ( k +1 ) +2(k+ 1)
2

INDUCTION IN MATHEMATICS AND THE CONCEPT OF RECURSION IN COMPUTER
SCIENCE
4
= ( k +1 ) (k +2)
2
This is similar to the statement and hence the proof has been successful
Next, it follows that the formula must hold for n = 1. Thus:
1 = ½· 1· 2
This ends the proof by induction hence the above formula is true for all positive integers
Recursion Algorithm
As earlier stated, Recursion in computer science and programming takes the approach of
defining a solution to a problem by considering the solutions of other similar problems but with a
smaller magnitude (Escardo & Oliva, 2010). For instance, when provided with a list of numbers
and the intention is to determine the smallest number, the consideration is that the smallest is
number is either the first one in the list or the smallest of the remaining numbers from the list.
The pseudo code of the algorithm is given as follows;
Function find_least( list )
possible_least_1 = first value in list
possible_least_2 = find_least ( rest of the list );
if ( possible_least_1 < possible_least_2 )
answer is possible_least_1
else
answer is possible_least_2

INDUCTION IN MATHEMATICS AND THE CONCEPT OF RECURSION IN COMPUTER
SCIENCE
5
end
end
It is important to note that in a recursion algorithm a computer has to keep in memory the output
of the previous statement. The major types of recursion in computer programming are tail, linear
and binary recursion; all of them have different functionalities in the programming world.
Relationship between Recursion and Induction
The relationship between these two terms stems from their very definition with both functions
elucidating similarities in structure and outputs. Further, mathematical induction can be used to
prove the validity of recursive procedures and algorithms in computer science. The use of
mathematical induction as a method of proof and construction of mathematical statements
closely follows the syntax of recursion in programming (Leron & Zazkis, 2010). The
construction of a mathematical phenomenon is usually premised on the properties of the objects
involved and more often, they will result in the conclusion of the mathematical theorem that is
under construction. Then it follows that the theorem is reduced to a mathematical problem which
is then solved following the logic of recursion, where a solution to the whole set is considered
from the point of the individual small units making up the whole theorem.
Ideally, recursion is meant to provide a solution to a problem that is there while induction, on the
other hand, validates whether the provided solution holds for positive integers. The fundamental
meeting of these two concepts is perhaps the structure of the functions. In recursion, the big

INDUCTION IN MATHEMATICS AND THE CONCEPT OF RECURSION IN COMPUTER
SCIENCE
6
problem is reduced to a subset of the problem and the search for a solution is considered from
this point of view. This is in comparison to a similar concept in induction where there has to be
an induction step which basically tests the induction hypothesis and attempts to prove the
theorem (Boyer & Moore, 2014). Further, in recursion, the procedure has to terminate, when the
solution to the easiest problem is found. This can be equally compared to the base step in
induction which is the easiest problem. Arguably, the induction and recursion process can be
considered to be similar in many ways than they are actually different. In essence, the recursion
process can be perceived to be the reverse of the induction process.
Conclusion
Mathematical induction and recursion in computer science are concepts that are profoundly
intertwined with very little differences separating them. In fact, the logic in the two concepts is
exact with both taking the same approach in the manner they carry out their functions. While
inductions are designed to validate mathematical statements, recursions are designed to provide
solutions in programming by representing the problem as a smaller problem. A recursion
procedure is repetitive and it starts with the problem ending up with the solution to it. Induction
starts with the theorem (solution) and ends up validating whether it holds or not by going back to
the statement (problem). Arguably, recursion can be considered to be a reverse induction
considering the sequence of steps involved in the process. Without, for individuals in computer
science a succinct understanding of these two concepts is imperative as it goes a long way in
improving the quality of algorithms made for application in different fields.

INDUCTION IN MATHEMATICS AND THE CONCEPT OF RECURSION IN COMPUTER
SCIENCE
7
References
Boyer, R. & Moore, S., 2014. A Computational Logic Handbook: Formerly Notes and Reports
in Computer Science and Applied Mathematics. Elsevier: s.n.
Escardo, M. & Oliva, P., 2010. Selection functions, bar recursion and backward induction.
Mathematical Structures in Computer Science, 20(2), pp. 127-168.
Henderson, P., n.d. The Role of Mathematics in Computer Science and Software Engineering
Education. Advances in Computers, Volume 65, pp. 349-395.
Leron, U. & Zazkis, R., 2010. Computational Recursion and Mathematical Induction. For the
Learning of Mathematics, 6(2), pp. 25-28.