Induction

2009-07-20 1:19 am


A sequence of real numbers {a(n)} is defined by

      a(1) = 7,   a(n) = 7^[ a(n- 1) ]   (n ≥ 2)

Prove by induction that for any m, n ≥ 2,

      a(m) - a(n) is divisible by 20.
更新1:

myisland8132: "We can write Then 2^c-2^d as 4^e-4^f=4^f(4^(e-f)-1) where e and f are even." I don't understand this step. Where do e and f come from? Is there something missing??

回答 (2)

2009-07-20 5:49 pm
✔ 最佳答案
Define b(n) = S(i = 1 to n)(74i-4 + 74i-3 + 74i-2 + 74i-1), i.e.
b(1) = 1 + 7 + 72 + 73
b(2) = 1 + 7 + 72 + 73 + 74 + 75 + 76 + 77, etc
Let Pr(n) be the proposition that b(n) is divisible by 20 for all n>=1.
Pr(1) is true since b(1) = 400 = (20)(20)
Assume Pr(k) is true, then b(k) = S(i = 1 to k)(74i-4 + 74i-3 + 74i-2 + 74i-1) = 20N where N is an integer.
Now b(k+1) = (74)b(k) + b(1) = (74)(20N) + 400 = 20(74N + 20) is divisible by 20.
So Pr(k+1) is true => b(n) is divisible by 20 for all integer >= 1… (1)
Let P(n) be the proposition that a(n) – a(2) is divisible by 20 for n>=2.
P(2) is true as a(2) – a(2) = 0.
Now assume P(k) is true for k>=2, i.e. a(k) – a(2) = 20P where P is an integer.
a(k) – a(2) = 20P = > a(k) = 20P + a(2)
Now for the statement P(k+1),
Since a(k+1) = 7a(k) then
a(k+1) – a(2) = 7a(k) – a(2)
= 720P + a(2) – a(2)
= (720P)(7a(2)) – a(2)
= (720P)a(3) – a(2)
= (720P)[a(3) – a(2)] + a(2)(720P – 1) … (2)
Firstly look at 720P – 1 = (7 – 1)(720P-1 + 720P-2 + … + 7 + 1) = 6b(5P) which is divisible by 20 per Pr(n) in (1) above. 720P – 1 = 20Q where Q is an integer.
Secondly look at a(3) – a(2)
a(1) = 7
a(2) = 77 = 823543
a(3) = 7823543
a(3) – a(2) = 7823543 – 77
= (77)(7823536) – 77
= (77)(7823536 – 1)
= (77)(7-1)(7823535 + 7823534 + … + 7 + 1)
= (77)(6)b(205884) is divisible by 20 = 20R where R is an integer.
It follows that equation (2) a(k+1) – a(2) = (720P)[a(3) – a(2)] + a(2)(720P – 1)
= (720P)(20R) + a(2)(20Q)
= 20[(720P)R + a(2)Q] is divisible by 20.
Therefore P(k+1) is true => P(n) is true for all n>=2.
a(m) – a(n) = [a(m) – a(2)] – [a(n) – a(2)] is also divisible by 20 for all m,n >= 2 (proved).
2009-07-21 8:42 pm
The following proof is using binomial theorem rather than induction.
Since 20=4*5, it justs need to show that a(m) - a(n) is divisible by 4 and 5
For divisible by 4, write a(m)=(8-1)^c and a(n)=(8-1)^d where c and d is odd numbers
Then a(m)-a(n)= (8-1)^c - (8-1)^d, using binomial theorem to expand it, then each term is divisible by 4 (since (-1)^c-(-1)^d=-1+1=0). The result follows
For divisible by 5, write a(m)=(5+2)^c and a(n)=(5+2)^d where c and d is odd numbers
Then a(m)-a(n)= (5+2)^c - (5+2)^d, using binomial theorem to expand it, then each term involves the factor 5 except the last term 2^c-2^d. Without loss of generality, let c>d. Since c and d are both odd and larger than 7, We acn write Then 2^c-2^d as 4^e-4^f=4^f(4^(e-f)-1) where e and f are even. This means that e-f are even and the unit-digit of 4^(e-f) is 6. So 4^f(4^(e-f)-1) is divisible by 5 and the result follows.
Combine two parts, we conclude that a(m) - a(n) is divisible by 20 for any m, n ≥ 2.


收錄日期: 2021-04-23 23:20:09
原文連結 [永久失效]:
https://hk.answers.yahoo.com/question/index?qid=20090719000051KK01247

檢視 Wayback Machine 備份