IT 102 George Mason University Recursive Python Function Question 1 You are to create a well-formed Python recursive function (i.e, there must be a stoppi

IT 102 George Mason University Recursive Python Function Question 1

You are to create a well-formed Python recursive function (i.e, there must be a stopping/base case and the recursive case must present a smaller problem), along with a call to that function.

Question 2

Trace your function and call. Remember that you must keep track of memory for each function call and provide output.

Question 3

Present a relationship with the domain some subset of the integers that is to be proven via Mathematical Induction.

Question 4

Prove your relationship with the domain some subset of the integers via Mathematical Induction. Note you must detail each of the four steps and show all of your work. IT102
Chapter 11: Recursion and Induction
RECURRENCE RELATIONS
•Function
•Domain: non-negative Integers
•Range: Real numbers
•Terms: given first one or two terms, then general term
•Examples:
1. Given: s1 = 1; sn = nsn-1, find s2 and s3
s2 = (2)s1
s2 = (2)(1) = 2
s3 = (3)s2
= (3)(2) = 6
2.
Given a1 = 2; an = 3 + an-1, find a3 and a4
a2 = 3 + a1 = 3 + 2 = 5
a3 = 3 + a2 = 3 + 5 = 8
a4 = 3 + a3 = 3 + 8 = 11
GEORGE MASON UNIVERSITY
RECURSION IN PYTHON
•Function that calls itself one or more times within its body
•Parameter(s): usually at least one non-negative Integer
•Base case: stopping condition
•Without it, there is infinite recursion
•Example:
•No Stopping Condition:
GEORGE MASON UNIVERSITY
RECURSION IN PYTHON
•Examples:
•With Stopping Condition:
•Recursive case: parameter used in recursive function call results in a smaller
problem to solve
GEORGE MASON UNIVERSITY
RECURSION IN PYTHON
•Almost never see a loop in a recursive function
•The repetition is created by the function calling itself
•Examples:
•Factorial
•Fibonacci
GEORGE MASON UNIVERSITY
RECURSION IN PYTHON
•Recurrence Relation: a1 = 3, an = an-1 + 3
•Python Function:
GEORGE MASON UNIVERSITY
TRACING A RECURSIVE FUNCTION
To really understand how code works: keep track of memory and output
Recursive calls : like a ‘cafeteria tray’
Example:
Each call provides a value for the parameter and has a result. The only output is
produced by the sole print statement
call: f(4)
n: 4
else:
20
return 2 * f(3)
call: f(3)
n: 3
else:
10
return 2 * f(2)
call: f(2)
n: 2
else:
return 2 * f(1)
5
call: f(1)
n: 1
if:
return 5
40
GEORGE MASON UNIVERSITY
MATHEMATICAL INDUCTION
•Used to prove a relationship (function) on non-negative integers
•Function with domain non-negative integers
•Given:
•Base (or Trivial) case : usually for n = 0, n = 1 for example
•Assumption for some positive integer (n = k)
•Proof of relationship for next integer (n = k+1)
•If it is true for the base case, and the assumption provides a proof for the next integer (i.e., if we
assume the relationship is true for n = k and that allows us to prove it is true for n = k + 1), then the
relationship must be true for all integers greater than or equal to the one used in the base case.
•For example
•given a relationship defined for a term in a sequence, n
•show true for trivial case (e.g., n = 1)
•assume true for some integer, n = k
•show true for next integer, n = k + 1
•Since the relationship was shown to be true for n = 1, and the assumption that it is true for n = k
provides the proof that the relationship is true for n = k + 1, by the principle of Mathematical Induction,
the relationship is true for all integers greater than or equal to 1
GEORGE MASON UNIVERSITY
MATHEMATICAL INDUCTION
•Example (sum):
GEORGE MASON UNIVERSITY
MATHEMATICAL INDUCTION
Example : Show that for all positive Integers:
1 + 3 + 5 + … + (2n – 1) = n2
a. Show that the relationship is true for the base case, where n = 1. When n = 1,
there is only one term, so the left hand side (LHS) is just 1. The right hand side
(RHS) is 12
1 = 12 So, the relationship holds for n = 1
b. Assume the relationship is true for some Integer k (i.e., n = k)
1 + 3 + 5 + … + (2k – 1) = k2
c.
Show that if the relationship is true for k then it is also true for n = k + 1
Show: 1 + 3 + 5 + … + (2k -1) + [2(k+1) – 1] ?= (k + 1)2
Using the assumption: 1 + 3 + 5 + … + (2k – 1) = k2
1 + 3 + 5 + … + (2k -1) + [2(k+1) – 1] ?= (k + 1)2
After substituting, the LHS:
k2 + [2(k + 1) – 1] ?= (k + 1)2
Simplify:
k2 + 2k + 2 – 1 ?= (k + 1)2
k2 + 2k + 1 ?= (k + 1)2
(k+1)2 = (k + 1)2
d. Therefore, by the Principle of Mathematical Induction, 1 + 3 + 5 +… n = n2 for
Integers, n > 1
GEORGE MASON UNIVERSITY
MATHEMATICAL INDUCTION
Example : Show that for all positive Integers:
n2 + n is divisible by 2
note: divisible by 2 ? multiple of 2, so can be written as 2*value
a. Show that the relationship is true for the base case, where n = 1. When n = 1,
12 + 1 = 2. 2 is divisible by 2. So, the relationship holds for n = 1
b. Assume the relationship is true for some Integer k (i.e., n = k)
k2 + k is divisible by 2
c.
Show that if the relationship is true for k then it is also true for n = k + 1
(k + 1)2 + (k + 1) is divisible by 2
Simplify by multiplying binomial out and then rearranging terms:
k2 + 2k + 1 + k + 1
k2 + k + 2k + 2
(k2 + k) + 2(k + 1)
Using the assumption: k2 + k is divisible by 2
(k2 + k)
+
2(k + 1)
divisible by 2
multiple of 2
So, (k + 1)2 + (k + 1) is divisible by 2
d. Therefore, by the Principle of Mathematical Induction,
n2 + n is divisible by 2 for Integers, n > 1
GEORGE MASON UNIVERSITY
MATHEMATICAL INDUCTION
Example : Show that for all positive Integers:
??
3 + 4 + 5 + … + (n + 2) = ??n(n + 5)
a.
Show that the relationship is true for the base case, where n = 1. When n = 1, there is only
??
one term, so the left hand side (LHS) is just 3. The right hand side (RHS) is (1)((1) + 5) = 3
??
3 = 3 — So, the relationship holds for n = 1
b. Assume the relationship is true for some Integer k (i.e., n = k)
??
3 + 4 + 5 + … + (k + 2) = ??k(k + 5)
c.
Show that if the relationship is true for k then it is also true for n = k + 1
??
Show: 3 + 4 + 5 + … + (n + 2)+ [(k + 1) + 2] ?= ??(k+1)((k+1)+ 5)
Using the assumption: 3 + 4 + 5 + … + (k + 2) = ????k(k + 5)
??
3 + 4 + 5 + … + (k + 2) + [(k + 1) + 2] ?= ??(k+1)((k+1)+ 5)
After substituting, the LHS:
??
k(k
??
??
+ 5)+ [(k + 1) + 2] ?= ??(k+1)((k+1)+ 5)
Simplify:
??
??
(???? + ????) + k + 3 ?= ??(k+1)((k+1)+ 5)
??
??
??
??
(????
+
????)
+
(2k
+
6)
?=
(k+1)((k+1)+ 5)
??
??
??
??
??
??
???? + ???? + ?? = ?? (?? + ??)(?? + ??) = ??(k+1)((k+1)+
??
5)
d. Therefore, by the Principle of Mathematical Induction,
??
??
3 + 4 + 5 + … + (n + 2) = n(n + 5) for Integers, n > 1
GEORGE MASON UNIVERSITY
MATHEMATICAL INDUCTION
•Example :
GEORGE MASON UNIVERSITY
CHAPTER 11 EXAMPLES
IT 102 Discrete Structures
RECURRENCE RELATIONS
Write the recurrence relation for the Arithmetic
Sequence: 10, 25, …
an
10
for n = 1
15 + an-1
for n > 1
=
GEORGE MASON UNIVERSITY
RECURRENCE RELATIONS
Write the recurrence relation for the Geometric
Sequence: 5, 20, …
bn
5
for n = 1
4*bn-1
for n > 1
=
GEORGE MASON UNIVERSITY
RECURRENCE RELATIONS
Write the recurrence relation for 3, 13, 43, 133,…
cn
5
for n = 1
4 + 3*cn-1
for n > 1
=
GEORGE MASON UNIVERSITY
RECURSIVE FUNCTIONS
Create a Python recursive function that prints all the integers less than or equal to
the value provided in the original call
GEORGE MASON UNIVERSITY
RECURSIVE FUNCTIONS
Create a Boolean Python recursive function to determine if an integer is a prime
number. Remember that a number is prime if it is greater than one and is only
divisible by itself and one.
GEORGE MASON UNIVERSITY
RECURSIVE FUNCTIONS
Create a Python recursive function to find the sum of the integers from 1 to any
given number.
GEORGE MASON UNIVERSITY
MATHEMATICAL INDUCTION
Show the following true via Mathematical Induction: 2n> n + 1, for n > 1
Step 1: Show true for n = 1
21 > 1 + 1 = 2
Step 2: Assume true for a random integer, k (this is the induction hypothesis)
Assume: 2k > k + 1
Step 3: Show true for n = k+1 (using the induction hypothesis)
Show:
2k+1 > (k+1) +1 = k + 2
2k > k + 1
(true by the induction hypothesis)
2 * 2k > 2*( k + 1) (multiply each side by 2)
2k+1 > 2k + 2
=k+k+2
>k+2
(since k > 1)
Step 4: Conclusion by the Principle of Mathematical Induction
Therefore by the Principle of Mathematical Induction, 2n> n + 1, for n > 1
GEORGE MASON UNIVERSITY
MATHEMATICAL INDUCTION
Show the following true via Mathematical Induction: 5n – 1 is divisible by 4, for n > 1
Step 1: Show true for n = 1
51 – 1 = 4, which is divisible by 4
Step 2: Assume true for a random integer, k (this is the induction hypothesis)
5k – 1 is divisible by 4
Step 3: Show true for n = k+1 (using the induction hypothesis)
Show:
5k+1 – 1 is divisible by 4
5k+1 – 1 = 5*5k – 1
= 4*5k + 1*5k – 1
divisible by 4 by the induction hypotheses
is divisible by 4
Step 4: Conclusion by the Principle of Mathematical Induction
Therefore by the Principle of Mathematical Induction, 5n – 1 is divisible by 4, for n > 1
GEORGE MASON UNIVERSITY
MATHEMATICAL INDUCTION
Show For an arithmetic sequence with first term a and common difference d, the
!(#$% !&’ ()
,
#
sum of the first n terms is:
Step 1: Show true for n = 1
a=
for n > 1
??(????% ??&?? ??)
??
Step 2: Assume true for a random integer, k (this is the induction hypothesis)
Assume: a + (a+d) + (a+2d) + … + (a+(k-1)d) =
??(????% ??&?? ??)
??
Step 3: Show true for n = k+1 (using the induction hypothesis)
Show: a + (a+d) + (a+2d) + … + (a+(k-1)d) + (a+kd) =
=
=
=
??(????% ??&?? ??)
+ (a+kd)
??
??????%??????? &????%????%??????
(??%??)(????% ??%??&?? ??) (??%??)(????%????)
=
??
??
(by the induction hypothesis)
??
(??%??)(????%????)
??
Step 4: Conclusion by the Principle of Mathematical Induction
Therefore by the Principle of Mathematical Induction,
??(????% ??&?? ??)
, for n > 1
?? GEORGE MASON UNIVERSITY
MATHEMATICAL INDUCTION
Show the following true via Mathematical Induction: 2+4+6+…+2n = n(n+1), for n > 1
Step 1: Show true for n = 1
2 = 1(1+1)
Step 2: Assume true for a random integer, k (this is the induction hypothesis)
Assume: 2+4+6+…+2k = k(k+1)
Step 3: Show true for n = k+1 (using the induction hypothesis)
Show:
2 + 4 + 6 +…+ 2k + 2(k+1) = (k+1)(k+2)
=k(k + 1)
+
2(k + 1) (by the induction hypothesis)
= k2 + k + 2k + 2
= k2 + 3k + 2
= (k+1)(k+2)
Step 4: Conclusion by the Principle of Mathematical Induction
Therefore by the Principle of Mathematical Induction,
2+4+6+…+2n = n(n+1), for n > 1
GEORGE MASON UNIVERSITY

Purchase answer to see full
attachment