1. Show all steps in calculating that 2.(1+3)=8 including justification of each step. Do not use any laws of arithmetic. Only use the definitions of addition and multiplication, together with abbreviations.
2. Prove that for all natural numbers n,
1+2+4+8+...+2n+1=2n+1.
(8 points)
3. Prove by induction on k that for every natural number k, there are natural numbers m and n, so that
2.k=(m+n).(m+n+1)+2.n.
(10 points)
4. The Fibonacci function is defined by the following recursion.
fib(2n+2)+fib(n)2=fib(n+2)2
and
fib(2n+1)+fib(n)2=fib(n+1)2
In these problem, we consider lists consisting only of natural numbers.
(10 points)
5.
Sets and Functions
Note: A function f: X->Y is onto if it is the case that for every b∈Y there is at least one a∈X so that f(a)=b. A function is one-to-one if it is that case that for every b∈Y, there is at most one a∈X so that f(a)=b.
6. Consider the sets A={0,1,2,3}and B={a,b,c}.
(8 points)
7.
(6 points)
8. Suppose you are given following functions: f:N->N,g:N->N and N->N defined by
f(m)=m2
g(m)=m+1
h(m)=2.m
m->m8+4
m->2m2+3
m->m4+4m2+4
m->4m2+4m+1
(8 points)
9. We write A ∼ B to mean that A and B are the same size (have the same cardinality). Write a clear and rigorous definition of what A ∼ B means in terms of functions. Do not give examples. Just write a mathematical definition
(6 points)
10.
(12 points)
11. We say that a set is countable if there is a one-to-one function f:A->N. We say that a set is denumerable if there is an onto function g:N->A.
(10 points)
Follow Us