Now,
2
2 2
1
1
10
2
1
1
2
1
1
1
3
3
k
k
k
k
k
k
+
= ⋅ > +





 ⋅
≥ +





 ⋅
≥ +





 ⋅
≥
+
≥ +
+
3
3
3
3
3
1
3
1
2
1
k
k
k
k
k
k
(
)
(
) .
Hence 2
10
3
n
n
n
>
≥
for
.
¨
Ì Exam ple 0.1.38: Prove that for every integer n ≥ 0, the number
4
3
2 1
2
n
n
+
+
+
is a multiple of 13.
Proof: We use induction on n, starting with n = 0.
P ( )
( )
( )
( )
0 4
3
4 3 13 1
2 0 1
0 2
2
=
+
= + =
+
+
(1)
Assume
P k
t
k
k
( ) =
+
=
+
+
4
3
13
2 1
2
, for some inte ger t.
(2)
We need to prove that
P k
k
k
(
) :
(
)
(
)
+
+
+ +
+ +
1 4
3
2
1 1
1 2 is a mul ti ple of 13.
Now,
4
3
4
3
4 4
4
2
1 1
1 2
2 1 2
2 1
2
2 1
2
(
)
(
)
(
)
(
)
(
)
k
k
k
k
k
+ +
+ +
+ +
+ +
+
+
=
+
=
+ (
)
3
3
3 3
2
2
2
k
k
k
+
+
+
−
+ ⋅
=
+
+
− +
=
+
−
+
+
+
+
4 4
3
3
4 3
16 13
3
13
2
2 1
2
2
2
2
(
)
(
)
( )
(
) [
k
k
k
k
t
from ( )]
[
]
2
13 16 3
2
=
−
+
t
k
(3)
From (3) it follows that P(k+1) is a multiple of 13. Hence we have,
4
3
2 1
2
n
n
+
+
+
is a multiple of 13.
¨
Ì Exam ple 0.1.39: Show that for any integer n
n
n
≥
+
+
+
0 11
12
2
2 1
, ( )
( )
is
divisible by 133.
Proof: Basis: When n = 0, 11
2 + 12
1 = 133 is divisible by 133.
Introduction
29