Scribd
Upload
2 views4 pages

Divisibility of Nn by 3n Proof

The document presents a proof by mathematical induction that the number Nn, which consists of 3n ones, is divisible by 3n. It starts with base cases for n=1 and n=2, establishes an induction hypothesis, and then proves the case for n=k+1. The conclusion asserts that the result holds for all natural numbers n.

Uploaded by

shabd.21
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views4 pages

Divisibility of Nn by 3n Proof

The document presents a proof by mathematical induction that the number Nn, which consists of 3n ones, is divisible by 3n. It starts with base cases for n=1 and n=2, establishes an induction hypothesis, and then proves the case for n=k+1. The conclusion asserts that the result holds for all natural numbers n.

Uploaded by

shabd.21
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Mathematical Induction

Prove that the number Nn = 111111……. (3n number of 1’s) is divisible by 3n.

We prove this by induction on ‘n’.

Consider n = 1

N1 = 111 = 3  37

N2 = 111111111 = 9  12345679 = 32  12345679

Notice that

Nn = 111111……. (3n number of 1’s)

= 1 + 10 + 100 + ………. + 1000…. (3n number of 0’s)

1, 10 , 100, 1000, ……… 1000…. (3n number of 0’s) is the geometric progression
containing 3n number of terms with initial term ‘1’ and common ratio = 10.
Hence this sum is given by

𝑛 𝑛
103 − 1 103 − 1
𝑁𝑛 = =
10 − 1 9
………………….. (A)

Induction hypothesis : Assume that P(k) is true, k  1.

That is assume that, Nk is divisible by 3k, k  1

That is, Nk = p  3k, where p  Z.

Note that
𝑘
103 − 1
𝑁𝑘 =
9
Next, consider n = k + 1 and the corresponding expression
𝑘+1 𝑘
103 −1 103 ×3 − 1
𝑁𝑘+1 = =
9 9

𝑘 3
(103 ) − 1
= 9
1 𝑘 𝑘 ×2 𝑘
= (103 − 1) (103 + 103 + 1)
9
2
3𝑘 𝑘
= (𝑁𝑘 ) [(10 − 1) + 3 × 103 ]

𝑘
= (𝑁𝑘 ) [(9𝑁𝑘 )2 + 3 × 103 ]
𝑘
= (𝑁𝑘 ) [81(𝑁𝑘 )2 + 3 × 103 ]
𝑘
= (𝑝 × 3𝑘 ) [81(𝑝 × 3𝑘 )2 + 3 × 103 ]
𝑘
= (𝑝 × 3𝑘 ) [81 × 𝑝2 × 32𝑘 + 3 × 103 ]
𝑘
= (3 × 𝑝 × 3𝑘 ) [27 × 𝑝2 × 3𝑘 + 103 ]
𝑘
= (𝑝 × 3𝑘+1 ) [27 × 𝑝2 × 3𝑘 + 103 ] ,

which is divisible by 3k+1.

Thus P(k + 1) is true.


Hence by Principle of Mathematical Induction, it follows that the result is true for
all natural numbers ‘n’.

You might also like