Problem 1.
Determine whether each of these proposed definitions is a valid recursive definition of a function f from the set of nonnegative integers to the set of integers. If f is well defined, find a formula for f(n) when n is a nonnegative integer and prove that your formula is valid.
a) f(0)=1, f(n)=2×f(n-2), for n ³ 1, n is even
f(n) = 2×f(n-2)= 2×2×f((n-2)-2)= 23×f(n-3×2) =24×f(n-4×2) =..2k×f(n-k×2)=
= 2(n-2)/2×f(2)= 2×2(n-2)/2
n-k×2 = 2; n = 2 + 2×k; n-2 = 2×k, k =(n-2)/2
b) f(0)=1, f(n) = f(n-1) – 1, for n ³ 1
f(n)= f(n-1) – 1= f(n-2)-2= f(n-k) –k = … = f(n-n) – n = 1 - n
n-k = 0, k=n
c) f(0)=2, f(1)=3, f(n)=f(n-1) – 1, for n ³ 2
f(n) = f(n-1) – 1= f(n-2)-2= f(n-k) –k = …… = f(n-(n-1)) – (n-1)= f(1) – n+1=4-n
n-k=1 , k = n-1
d) f(0)=1, f(1)=2, f(n)= 2×f(n-2), for n ³ 2
f(n) = 2×f(n-2) = …. =24×f(n-4×2) = 2k×f(n-k×2) = 2n/2
n-k×2 = 0 ……..
e) f(0)=1, f(n)= 3×f(n-1) if n is odd and n ³ 1 and f(n)= 9×f(n-2) if n is even and n ³ 2
Problem 2.
Give a recursive definition of the sequence {an}, n=1,2,3… if
a) an = 6n
a0=0 ; an+1 = 6(n+1)=6n + 6 = an + 6
b) an = 2n +1
a0 = 1; an+1 = 2(n+1) + 1 = (2n +1) + 2 = an + 2
c) an = 10n
a0 = 1 ; an+1 = 10n+1 = 10n×10 = 10×an
d) an = 5
Problem 3.
Assuming that fn is the nth Fibonacci number [f0=f1=1; fn+1= fn+ fn-1],
prove that f02 + f12 + … + fn2 = fn×fn+1
when n is a positive integer.
Basic step: f02 = 12 = f0×f1 =1×1=1
Inductive step: assumption - f02 + f12 + … + fn2 = fn×fn+1
We have to prove: f02 + f12 + …+ fn2 + fn+12 = fn+1×fn+2
fn×fn+1+ fn+12 = fn+1×fn+2 = fn+1×(fn+1+ fn)
Problem 4.
Give a recursive definition of
a) the set S of odd positive integers
1 Î S, k Î S ® k+2 ÎS
b) the set S of positive integer powers of 3
S = {31, 32, …}
3 Î S , k Î S ® 3k Î S
c) the set S of polynomials with integer coefficients
S = {a0 + a1x + a2x2 +…. akxk : ("i £ k)[ai Î N]}
a ÎN, k Î N È {0} ® axk Î S
s1 , s2 Î S ® s1 + s2 Î S
Problem 5.
Give a recursive definition of each of these sets of ordered pairs of positive integers. Use structural induction to prove that the recursive definition you found is correct.
[Hint: To find a recursive definition, plot the points in the set in the plane and look for paterns]
a) S={(a,b): aÎZ+, bÎZ+, and a+b is even}
(1,1) Î S, (2,2) Î S,
(p,q) Î S ® (p, q+2) Î S, (p+2,q) Î S
b) S={(a,b): aÎZ+, bÎZ+, and a or b is odd}
(1,1) Î S, (1,2) Î S, (2,1) Î S
(p,q) Î S ® (p, q+2) Î S, (p+2,q) Î S
c) S={(a,b): aÎZ+, bÎZ+, a+b is odd, 3½b}
(2,3) Î S , (1,6) Î S
(p,q) Î S ® (p,q+6) Î S, (p+2,q) Î S
Problem 6.
Give a recursive algorithm for finding the sum of the first n positive integers
Procedure S(n: integer)
if n=1 then S(n):=1
else S(n):= S(n-1) + n
Problem 7.
Give a recursive algorithm for finding the minimum of a finite set of integers, making use of the fact that the minimum of n integers is the smaller of the last integer in the list and the minimum of the first n-1 integers in the list.
Procedure S(a1,a2,…,an: integers)
if n=1 then S(a1,a2,…,an):=a1
else S(a1,a2,…,an):= min(S(a1,a2,…,an-1), an)
Problem 8.
Device a recursive algorithm for computing n2 where n is a nonnegative integer using the fact that (n+1)2 = n2 + 2n + 1.
Procedure S(n: nonnegative)
if n=0 then S(n):= 0
else S(n):= S(n-1) + 2(n-1) + 1
Problem 9.
Device a recursive algorithm to find the nth term of the sequence defined by a0=1, a1=2, an = an-1×an-2, for n=2,3,4,….
Procedure S(n: nonnegative)
if n=0 then S(n):= 1
else if n=1 then S(n):= 2
else S(n):= S(n-1) × S(n-2)