Induction in Mathematics and the Concept of Recursion in Computer Science

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