Determine whether each of these proposed definitions is a valid recursive defini- tion of a function f from the set of nonnegative integers to the set of integers.
(a) f(0) = 1, f(n) = −f(n − 1) for n ≥ 1.
(b) f(0) = 1, f(1) = 0, f(2) = 2, f(n) = 2f(n − 3) for n ≥ 3. (c) f(0) = 0, f(1) = 1, f(n) = 2f(n + 1) for n ≥ 2.
(d) f(0) = 0, f(1) = 1, f(n) = 2f(n − 1) for n ≥ 1.
Copyright By PowCoder代写 加微信 powcoder
Give a recursive definition of the sequence {an}, n = 1, 2, 3, … if (a)an =4n−2.
(b) an = 1 + (−1)n.
(c)an =n(n+1).
(d) an = n2. Problem 3
Give a recursive definition of
(a) the set of odd positive integers.
(b) the set of positive integer powers of 3.
1/3 CSI2101/UOttawa/MdH/S22
Use structural induction to prove that (w1w2)R = w2Rw1R. Problem 5
Show that (wR)i = (wi)R whenever w is a string and i is a nonnegative integer; that is show that the i-th power of the reversal of a string is the reversal of the i-th power of the string.
Verify that the program segment
if x < y then bb min := x else
bb min := y
is correct with respect to the initial assertion T and the final assertion (x ≤ y ∧ min = x) ∨ (x > y ∧ min = y).
Suppose that both the conditional statement p0 → p1 and the program assertion p1{S}q are true. Show that p0{S}q also must be true.
Problem 8 (in-class task!)
This program computes quotients and remainders.
2/3 CSI2101/UOttawa/MdH/S22
while r ≥ d bb r := r − d bb q := q + 1
Verify that it is partially correct with respect to the initial assertion “a and d are positive integers” and the final assertion “q and r are integers such that a = dq + r and 0 ≤ r < d.”
3/3 CSI2101/UOttawa/MdH/S22
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com