Natural Number and Induction Homework Help
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.
![Natural Number And Induction Natural Number And Induction img1](https://www.urgenthomework.com/webimg/uah/math/natural-number-and-induction-img1.jpg)
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.
![Natural Number And Induction Natural Number And Induction img2](https://www.urgenthomework.com/webimg/uah/math/natural-number-and-induction-img2.jpg)
- Construct a table of the first 10 values of fib(n).
- Show that for every natural number n,
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.
- We want to define the sum of such a list to mean the obvious thing: Σ([2,3,4])=9. Write a formal recursive definition of Σ(K).
- Using your definition, prove that for any two lists of natural numbers, Σ(K+L)=Σ(K)+Σ(L).
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}'}.
- Write out the set B X A using correct notation.
- Draw a picture of a function from A to B that is not a bijection (not a matching).
- Is there a bijection between A and B. Explain your answer.
- How many functions are there from B to A? Explain your answer.
- How many onto functions are there from B to A.
(8 points)
7.
- Given two sets C and D for which C X D is equal to D X C.
- Show that for any two sets A and B, it is the case that there is a bijection from A X B to B X A.
(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
- Using composition only (that is, by writing expressions like g o g o h), define new functions that calculate the following
- Is it possible to define {'m ->m'}3 using composition and these three functions ? Explain why or why not.
{'m->m'}8+4
{'m->2m'}2+3
{'m->m'}4+4m2+4
{'m->4m'}2+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.
- For sets A and{' B = {0,1}'}, define a one-to-one function {'F:A->B'}A.
- Show that F is not also onto.
- Show that three is no onto function from A to BA.
(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'}.
- Show that every denumerable set is countable.
- Show that every non-empty countable set is denumerable.
(10 points)
Math Tutorials
- Math - Polynomials
- Math - Series and Sequences
- Math - Dividing Polynomials
- Math - Factoring Polynomials
- Math - Solving Quadratics
- Math - Solving Inequalities
- Math - Solving Equations
- Math - Complex Numbers
- Math - Matrix
- Math - Inverse Functions
- Math - Graphing Quadratic Functions
- Math - Graphing Polynomial Functions
- Math - Functions
- Math - Exponentials and Logarithms
- Math - Cramer's Rule
- Math - Absolute Value & Inequalities