Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.28

28.  Show that the union of two countable sets is countable.

Solution: We assume that A and B are two countable sets.
We will consider following cases.
Case 1:
If bothA and B are finite, then A\cup B is finite and hence countable.
Case 2:
We assume that one of A and B is finite and the other is countable infinite. We assume without loss of generality that A is finite.
Since B is countably infinite, there exists a function
f:B \rightarrow \mathbb{Z^+}
This is a one-to-one correspondence, that is,
f(b_i)=i
For b_i \epsilon B and i \epsilon \mathbb{Z^+}
Let us consider
C=A-B
Thus,
A \cup B = B\cup C
If C= Ø
Then A \cup B = B
This is countably infinite.
Therefore, we assume that C\neq Ø
Also we suppose that
C=\left \{ c_1,c_2,...,c_n \right \}
We consider the function
g:B \cup C \rightarrow \mathbb{Z^+}
Where g(c_j)=j
And g(b_i)=n+i
Clearly, g is one-to-one and onto.
Thus,B \cup C is countable.
But B \cup C = A \cup B
So, A \cup B is countable.
Case 3:
We suppose that both A and B are infinite and A\cap B= Ø
Since A and B are both countable, there exist functions
p:\mathbb{Z^+} \rightarrow A
q:\mathbb{Z^+} \rightarrow B
These are one-to-one correspondences.
We also consider the function
r:\mathbb{Z^+} \rightarrow A \cup B
Where r(n)=p\left ( \frac{n}{2} \right )
If n is even
And r(n)=q\left ( \frac{n+1}{2} \right )
If n is odd
Since p,q are one-to-one, so r is also one-to-one.
Similarly, since p,q are onto, so r is also onto.
Therefore, r is a one-to-one correspondence, and hence,r is countable.
Case 4:
We suppose that both A and B are infinite and A \cap B= Ø
We assume that C=B-A
Then,
A \cup B= A \cup C
And
A \cap C= Ø
If C is countably infinite, then
A \cup B= A \cup C
Is countable by the previous case
If C is finite, then
A \cup B= A \cup C
Is countable by case 2
Therefore, A \cup B is countable.

Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.27

27. Show that the set of all numbers of the form a+b\sqrt{2} where a and b are integers, is countable.

Solution: We shall first prove a proposition.
We assume that A is a non-empty set. Then the following are equivalent.
(a) A is countable
(b) there exists a surjection f: \mathbb{Z^+} \rightarrow A
(c) there exists an injection g: A \rightarrow \mathbb{Z^+}

Proof
(a) \Rightarrow (b)
If A is countably infinite, then there exists a bijection
f: \mathbb{Z^+} \rightarrow A
And then (b) follows
If A is finite, then there is a bijection
h:\left \{ 1,...,n \right \} \rightarrow A
For some n
Then the function f: \mathbb{Z^+} \rightarrow A defined by
f\left (i \right )=\left\{\begin{matrix} h\left (i \right ) & 1\leq i \leq n\\ h\left (n \right ) & i> n \end{matrix}\right.
Is a surjection
(b) \Rightarrow (c)
We assume that f: \mathbb{Z^+} \rightarrow A is a surjection. We claim that there is an injection g: A \rightarrow \mathbb{Z^+}
To define g we note that if
a\epsilon A
Then
f^{-1}(\left \{a \right \})\neq \phi
Hence, we set
g(a)=min f^{-1}(\left \{a \right \})
Now we note that if
a \neq a'
Then
f^{-1}(\left \{ a \right \})\bigcap f^{-1}(\left \{ a' \right \})=\phi
Implies
min f^{-1}(\left \{ a \right \})\neq min f^{-1}(\left \{ a' \right \})
Hence
g(a)\neq g(a')
And g: A \rightarrow \mathbb{Z^+} is an injection
(c) \Rightarrow (a)
We assume that g: A \rightarrow \mathbb{Z^+} is an injection. We want to show that A is countable.
Since
g:A \rightarrow g(A)
Is a bijection and
g(A)\subset \mathbb{Z^+}
That is, the subset of a countable set is countable.
So, A is countable.
This ends the proposition.
We now show that the set of all numbers of the form a+b\sqrt{2} where a,b are integers, is countable.
By the above proposition it suffices to construct an injective function
f:\mathbb{Z^+}\times \mathbb{Z^+} \rightarrow \mathbb{Z^+}
We define it as
f(a,b)=2^a3^b
We assume that
2^a3^b=2^c3^d
If
a<c
Then
3^b=2^{c-a}3^d
The left side of this equality is an odd number where as the right side is an even number implying
a=c
And
3^b=3^d
Then also
b=d
Hence, f is injective and so set of all numbers of the form a+b\sqrt{2} where a,b are integers, is countable.

Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.26

26. Show that the set of all rational numbers of the form n/5, where n is an integer, is countable.

Solution:

We have to show that the set of all rational numbers of the form n/5 where n is an integer, is countable.
We shall first prove a proposition.
We assume that A is a non-empty set. Then the following are equivalent.
(a) A is countable
(b) there exists a surjection f: \mathbb{Z^+} \rightarrow A
(c) there exists an injection g: A \rightarrow \mathbb{Z^+}

Proof
(a) \Rightarrow (b)
If A is countably infinite, then there exists a bijection
f: \mathbb{Z^+} \rightarrow A
And then (b) follows
If A is finite, then there is a bijection
h:\left \{ 1,...,n \right \} \rightarrow A
For some n
Then the function f: \mathbb{Z^+} \rightarrow A defined by
f\left (i \right )=\left\{\begin{matrix} h\left (i \right ) & 1\leq i \leq n\\ h\left (n \right ) & i> n \end{matrix}\right.
Is a surjection
(b) \Rightarrow (c)
We assume that f: \mathbb{Z^+} \rightarrow A is a surjection. We claim that there is an injection g: A \rightarrow \mathbb{Z^+}
To define g we note that if
a\epsilon A
Then
f^{-1}(\left \{a \right \})\neq \phi
Hence, we set
g(a)=min f^{-1}(\left \{a \right \})
Now we note that if
a \neq a'
Then
f^{-1}(\left \{ a \right \})\bigcap f^{-1}(\left \{ a' \right \})=\phi
Implies
min f^{-1}(\left \{ a \right \})\neq min f^{-1}(\left \{ a' \right \})
Hence
g(a)\neq g(a')
And g: A \rightarrow \mathbb{Z^+} is an injection
(c) \Rightarrow (a)
We assume that g: A \rightarrow \mathbb{Z^+} is an injection. We want to show that A is countable.
Since
g:A \rightarrow g(A)
Is a bijection and
g(A)\subset \mathbb{Z^+}
That is, the subset of a countable set is countable.
So, A is countable.
This ends the proposition.
We define the function
f:\mathbb{Z} \times \mathbb{Z^+}\rightarrow \mathbb{Q}
As
f(n,5)=n/5
Since each rational number is of the form n/5 for some n \epsilon \mathbb{Z}, it follows that f is surjective.
Since \mathbb{Z} \times \mathbb{Z^+} is countably infinite, that is, the Cartesian product of countable sets is countable, it follows from part (b) of the above proposition and replacing \mathbb{Z^+} by an arbitrary countably infinite set (using composition of functions), that rational numbers of the form n/5 is countable.

 

Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.25

25. Show that the set of all integers greater than -100 is countable.

Solution: In order to prove that the set of all integers greater than -100 is countable, it suffices to prove that the set of integers \mathbb{Z} is countable. This follows from the fact that the subset of a countable set is countable.

We can the list the integers in a sequence
0,1,-1,2,-2,3,-3,…
We define a function
f:\mathbb{N} \rightarrow \mathbb{Z}

This is defined as
f(n)=\left\{\begin{matrix} \frac{n}{2}&\text{n is even} \\ \frac{-(n-1)}{2}& \text{n is odd}\end{matrix}\right.

We now show that f is a bijection.
First we show that it is injective by case analysis on the parity of \mathbb{N}
Case 1
If m,n are two even natural numbers
Then
f(m)=\frac{m}{2}
f(n)=\frac{n}{2}
It follows that
f(m)=f(n)
Implies that
m=n
Case 2
If m,n are two odd natural numbers
Then
f(m)=-\frac{m-1}{2}
f(n)=-\frac{n-1}{2}
It follows that
f(m)=f(n)
Implies that
m=n
Therefore f is injective.
We now show that f is surjective by case analysis on the sign of some integer t in \mathbb{Z}
Case 1
If t is positive, then t will appear in an even position in the sequence.
Thus,
f(2k)=\frac{2k}{2}
=t
With
t=k
This implies that for every positive value t in \mathbb{Z} there is a natural number 2k
Case 2
If t is negative, then t will appear in an odd position in the sequence.
Thus,
f(2k-1)=-\frac{(2k-1)-1}{2}
=t
With
t=-k
This implies that for every negative value t in \mathbb{Z} there is a natural number 2k-1
Therefore, f is surjective
Hence, \mathbb{Z} is countable set.
Now we define the sequence
a_n=n-100
>-100
For n \in \mathbb{N}
This is clearly a subset of \mathbb{Z} and so is countable.

Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.24

24. Find three different formulas or rules for the terms of a sequence a_n if the first three terms of this sequence are 2, 3, 6.

Solution: We consider the first three terms of a sequence 2,3,6.
The simplest form of this sequence is
a_n=2^{n}-(n-1)
For n=1,2,3,...
We can even use recursive formula for this sequence, that is,
a_1=2
a_2=3
a_n=a_{n-1}.a_{n-2}
For n \geq 3
We can also formulate the nth term of this sequence by inserting factorials and doing inspection.
2=\frac{(1+1)!}{2^0}
3=\frac{(2+1)!}{2^1}
6=\frac{(3+1)!}{2^2}
Therefore, we have for n=1,2,3,...
a_n=\frac{(n+1)!}{2^{n-1}}

Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.23

23. Find three different formulas or rules for the terms of a sequence {a_n}  if the first three terms of this sequence are  1,2,4.

Solution: We consider the first three terms of a sequence as 1,2,4

The simplest form of this sequence is

a_n=2^{n-1}
For n=1,2,3,...
We can even use recursive formula for this sequence, that is,
a_1=1
a_2=2
a_n=a_{n-1}+2a_{n-2}
For n \geq 3
We can also formulate the nth term of this sequence by inspection.
1=\frac{1^2-1+2}{2}
2=\frac{2^2-2+2}{2}
4=\frac{3^2-3+2}{2}
Therefore, we have for n=1,2,3,...
a_n=\frac{n^2-n+2}{2}

Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.22

22. Conjecture a formula for the nth term of {a_n}  if the first ten terms of this sequence are as follows.

a) 2, 6, 18, 54, 162, 486, 1458, 4374, 13122, 39366
b) 1, 1, 0, 1, 1, 0, 1, 1, 0, 1
c) 1, 2, 3, 5, 7, 10, 13, 17, 21, 26
d) 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365

Solution:

(a) 2, 6, 18, 54,162,486,1458,4374,13122,39366

We can see that this sequence is neither in arithmetic progression nor in geometric Progression. We use the method of inspection to find the

nth term of this sequence.

2=2(3^0)
6=2(3^1)
18=2(3^2)
54=2(3^3)
162=2(3^4)
486=2(3^5)
1458=2(3^6)
4374=2(3^7)
13122=2(3^8)
39366=2(3^9)

Therefore we have for n=1,2,...,10

a_n=2(3^{n-1})

(b) 1,1,0,1,1,0,1,1,0,1

This sequence contains 0’s and 1’s only. We notice that 0 occurs in third multiple term of the sequence.
Therefore, we have for n=1,2,...,10

a_n = \left\{\begin{matrix}0; n=3m&for& m=1,2,3 & \\1; otherwise & \end{matrix}\right.

(c) 1, 2, 3,5,7,10,13,17,21,26

We can see that this sequence is neither in arithmetic progression nor in geometric Progression. We split the sequence into odd and even terms and use the method of inspection to find the nth term of this sequence. Now, for 1,3,7,13,21 we have

1=1^2-0
3=2^2-1
7=3^2-2
13=4^2-3
21=5^2-4

So the odd termed sequence is of the form

a_{2n-1} = n^2-(n-1)
Where n=1,2,3,4,5
Similarly, for 2,5,10,17,26 we have

2=1^2+1
5=2^2+1
10=3^2+1
17=4^2+1
26=5^2+1

So the even termed sequence is of the form

a_{2n}=n^2+1
where n=1,2,3,4,5
Therefore, we have for n=1,2,…,10

a_n = \left\{\begin{matrix} a_{2m-1} = m^2-(m-1),m=1,2,3,4,5 & \\ a_{2m} = m^2 + 1,m=1,2,3,4,5 & \end{matrix}\right.

(d) 3, 5,11,21,43,85,171,341,683,1365

We can see that this sequence is neither in arithmetic progression nor in geometric Progression. We use the method of inspection to find the nth term of this sequence.

5=2.3-(-1)^2
11=2.5-(-1)^3
21=2.11-(-1)^4
43=2.21-(-1)^5
85=2.43-(-1)^6
171=2.85-(-1)^7
341=2.171-(-1)^8
683=2.341-(-1)^9
1365=2.683-(-1)^10

Therefore we have for n=1,2,….,10

a_1=3,a_n=2a_{n-1}-(-1)^n, n \geq 2

Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.21

21. Conjecture a formula for the nth term of {a_n} if the first ten terms of this sequence are as follows.
a) 3, 11,19,27,35,43,51,59,67,75
b) 5, 7, 11, 19, 35,67, 131,259,515, 1027
c) 1,0,0, 1,0,0,0,0,1,0
d) 1, 3,4,7,11,18,29,47,76,123

Solution:

(a) 3,11,19,27,35,43,51,59,67,75

We can see that this sequence is neither in arithmetic progression nor in geometric Progression. We use the method of inspection to find the nth term of this sequence.

3=8(1)-5
11=8(2)-5
19=8(3)-5
27=8(4)-5
35=8(5)-5
43=8(6)-5
51=8(7)-5
59=8(8)-5
67=8(9)-5
75=8(10)-5

Therefore we have for n=1,2,3,...,10
a_n=8n-5

(b) 5, 7,11,19,35,67,131,259,515,1027

We can see that this sequence is neither in arithmetic progression nor in geometric Progression. We use the method of inspection to find the nth term of this sequence.

5=2+3
7=2^2+3
11=2^3+3
19=2^4+3
35=2^5+3
67=2^6+3
131=2^7+3
259=2^8+3
515=2^9+3
1027=2^{10}+3

Therefore we have for n=1,2,3,...,10
a_n=2^n+3

(c) 1,0,0,1,0,0,0,0,1,0
We can see that this sequence is neither in arithmetic progression nor in geometric Progression. It might strike to use greatest integer function here. We observe that For perfect squares the value turns out to be 1 otherwise it is 0. So, we use the method of inspection to find the nth term of this sequence.
1=[[\sqrt{1}]/\sqrt{1}
0=[[\sqrt{2}]/\sqrt{2}
=[1/\sqrt{2}]

0=[[\sqrt{3}]/\sqrt{3}]
=[1/\sqrt{3}]
1=[[\sqrt{4}]/\sqrt{4}]
=[2/2]

0=[[\sqrt{5}]/\sqrt{5}]
=[2/\sqrt{5}]
0=[[\sqrt{6}]/\sqrt{6}]
=[2/\sqrt{6}]

0=[[\sqrt{7}]/\sqrt{7}]
=[2/\sqrt{7}]

0=[[\sqrt{8}]/\sqrt{8}]
=[2/2 \sqrt{2}]
=[1/\sqrt{2}]

1=[[\sqrt{9}]/\sqrt{9}]
=[3/3]

0=[[\sqrt{10}]/\sqrt{10}]
=[3/\sqrt{10}]

Therefore we have for n=1,2,...10

a_n=[[\sqrt{n}]/\sqrt{n}]

(d) 1, 3,4,7,11,18,29,47,76,123

We define Lucas numbers recursively by

L_n = L_{n-1} + L_{n-2}
For n \geq 3 with
L_1 =1
L_2 =3
Now, we use the recursive formula to find the successive numbers.
That is,

L_3 = L_2 + L_1
= 3 + 1
= 4

L_4 = L_3 + L_2
= 4 + 3
= 7

L_5 = L_4 + L_3
= 7 + 4
= 11

L_6 = L_5 + L_4
= 11 + 7
= 18

L_7 = L_6 + L_5
= 18 + 11
= 29

L_8 = L_7 + L_6
= 29 + 18
= 47

L_9 = L_8 + L_7
= 47 + 29
= 76

L_10 = L_9 + L_8
= 76 + 47
= 123

Replacing L_n with a_n we have
a_n = a_{n-1} + a_{n-2}

For n \geq 3 with
a_1 = 1
a_2 = 3

Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.20

20. Show that if m is a positive integer,then [mx] = [x] + [x + (1/m) ] + [x + ( 2/m) ] + · · ·+ [x + (m - 1) /m] whenever x is a real number.
Solution:

We have to show that m if is a positive integer, then
[mx]=[x]+[x+(1/m)]+[x+(2/m)]+...+[x+(m-1)/m]….(1)
Whenever x is a real number
We consider
x=[x]+{x}
Where [x] is the greatest integer part of x and {x} is the fractional part of x
We also know that
[integer+(...)]=integer+[(...)]
We now, consider the right hand side of (1)
RHS=[[x]+{x}]+[[x]+{x}+1/m]+[[x]+{x}+2/m]+...
+[[x]+{x}+(m-1)/m]
=m[x]+[{x}]+[{x}+1/m]+[{x}+2/m]+...+[{x}+(m-1)/m]
=m[x]+[{x}]+[{x}+1/m]+[{x}+2/m]+...+[{x}+p/m]+...
+[{x}+(m-1)/m]
Where p is the minimum value such that
[{x}+p/m]=1
Proceeding further, we get,
RHS=m[x]+0+0+0+...p times+[{x}+p/m]+...
+[{x}+(m-1)/m]
=m[x]+1+1+1+...(m-p) times
=m[x]+m-p
Now, since,
[{x}+p/m]=1
Implies that
[{x}+(p/m)-1]=0
[{x}-((m-p)/m)]0
Which in turn implies that
{x}=(m-p)/m+(<1/m) for p to be minimum
m{x}=m-p+(<1)
[m{x}]=m-p …. (2)

Therefore, by (2) we get

RHS=m[x]+[m{x}]
=[m[x]]+[m{x}]
=[m[x]+m{x}]
=[mx]
Hence, we have prove (1)

Elementary Number Theory and Its Application, 6th Edition by Kenneth H. Rosen Exercises 1.1.19

19. Show that [\sqrt{[x]}]=[\sqrt{x}] whenever x is a nonnegative real number.
Solution:  We have to prove the equation
[\sqrt{[x]}]=[\sqrt{x}]
Whenever x is a non-negative real number
We assume that
x=k+\epsilon
Where k is an integer and
0<=\epsilon<1
Further, we assume that
k=a^2+b
Where a is the largest integer such that
a^2<=k
Now,
a^2<=k
=a^2+b
<=x
=a^2+b+\epsilon
a^2<(a+1)^2
This implies that
[\sqrt{x}] = a
And
[\sqrt{[x]}]=[\sqrt{k}]
=a
Hence we have achieved the equality in the equation
[\sqrt{[x]}]=[\sqrt{x}]