Menu Close

prove-by-mathematical-induction-7-n-3n-4-4-n-1-divided-by-9-




Question Number 111132 by bemath last updated on 02/Sep/20
prove by mathematical induction  ⇒ 7^n −(3n+4)×4^(n−1)  divided by 9
$$\mathrm{prove}\:\mathrm{by}\:\mathrm{mathematical}\:\mathrm{induction} \\ $$$$\Rightarrow\:\mathrm{7}^{\mathrm{n}} −\left(\mathrm{3n}+\mathrm{4}\right)×\mathrm{4}^{\mathrm{n}−\mathrm{1}} \:\mathrm{divided}\:\mathrm{by}\:\mathrm{9} \\ $$
Answered by john santu last updated on 02/Sep/20
let p(n) = 7^n −(3n+4).4^(n−1)   (1)p(1) = 7−(3.1+4).4^0 = 7−7=0 (true)  (2) assume for n=k →p(k) divisible by 9  we have p(k)=7^k −(3k+4).4^(k−1) ≡ 9m , m∈Z                              =7^k −3k.4^(k−1) −4^k ≡ 9m               = 7^k −4^k −3k.4^(k−1)  ≡ 9m  (3) we want to prove for n=k+1   p(k+1) is divisible by 9  p(k+1)=7^(k+1) −(3(k+1)+4).4^k   ⇔ 7.7^k −(3k+4+3).4^k   ⇔7.7^k −(3k+7).4^k   ⇒7.7^k −3k.4^k −7.4^k   ⇒7(7^k −4^k )−3k.4^k   ⇒ 7(7^k −4^k −3k.4^(k−1) )+21k.4^(k−1) −3k.4^k   ⇒7(9m)+3k.4^(k−1) (7−4)  ⇒63m+9k.4^(k−1)   ⇒9(7m+k.4^(k−1) ) is divisible by 9.  q.e.d
$${let}\:{p}\left({n}\right)\:=\:\mathrm{7}^{{n}} −\left(\mathrm{3}{n}+\mathrm{4}\right).\mathrm{4}^{{n}−\mathrm{1}} \\ $$$$\left(\mathrm{1}\right){p}\left(\mathrm{1}\right)\:=\:\mathrm{7}−\left(\mathrm{3}.\mathrm{1}+\mathrm{4}\right).\mathrm{4}^{\mathrm{0}} =\:\mathrm{7}−\mathrm{7}=\mathrm{0}\:\left({true}\right) \\ $$$$\left(\mathrm{2}\right)\:{assume}\:{for}\:{n}={k}\:\rightarrow{p}\left({k}\right)\:{divisible}\:{by}\:\mathrm{9} \\ $$$${we}\:{have}\:{p}\left({k}\right)=\mathrm{7}^{{k}} −\left(\mathrm{3}{k}+\mathrm{4}\right).\mathrm{4}^{{k}−\mathrm{1}} \equiv\:\mathrm{9}{m}\:,\:{m}\in\mathbb{Z} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:\:=\mathrm{7}^{{k}} −\mathrm{3}{k}.\mathrm{4}^{{k}−\mathrm{1}} −\mathrm{4}^{{k}} \equiv\:\mathrm{9}{m} \\ $$$$\:\:\:\:\:\:\:\:\:\:\:\:\:=\:\mathrm{7}^{{k}} −\mathrm{4}^{{k}} −\mathrm{3}{k}.\mathrm{4}^{{k}−\mathrm{1}} \:\equiv\:\mathrm{9}{m} \\ $$$$\left(\mathrm{3}\right)\:{we}\:{want}\:{to}\:{prove}\:{for}\:{n}={k}+\mathrm{1}\: \\ $$$${p}\left({k}+\mathrm{1}\right)\:{is}\:{divisible}\:{by}\:\mathrm{9} \\ $$$${p}\left({k}+\mathrm{1}\right)=\mathrm{7}^{{k}+\mathrm{1}} −\left(\mathrm{3}\left({k}+\mathrm{1}\right)+\mathrm{4}\right).\mathrm{4}^{{k}} \\ $$$$\Leftrightarrow\:\mathrm{7}.\mathrm{7}^{{k}} −\left(\mathrm{3}{k}+\mathrm{4}+\mathrm{3}\right).\mathrm{4}^{{k}} \\ $$$$\Leftrightarrow\mathrm{7}.\mathrm{7}^{{k}} −\left(\mathrm{3}{k}+\mathrm{7}\right).\mathrm{4}^{{k}} \\ $$$$\Rightarrow\mathrm{7}.\mathrm{7}^{{k}} −\mathrm{3}{k}.\mathrm{4}^{{k}} −\mathrm{7}.\mathrm{4}^{{k}} \\ $$$$\Rightarrow\mathrm{7}\left(\mathrm{7}^{{k}} −\mathrm{4}^{{k}} \right)−\mathrm{3}{k}.\mathrm{4}^{{k}} \\ $$$$\Rightarrow\:\mathrm{7}\left(\mathrm{7}^{{k}} −\mathrm{4}^{{k}} −\mathrm{3}{k}.\mathrm{4}^{{k}−\mathrm{1}} \right)+\mathrm{21}{k}.\mathrm{4}^{{k}−\mathrm{1}} −\mathrm{3}{k}.\mathrm{4}^{{k}} \\ $$$$\Rightarrow\mathrm{7}\left(\mathrm{9}{m}\right)+\mathrm{3}{k}.\mathrm{4}^{{k}−\mathrm{1}} \left(\mathrm{7}−\mathrm{4}\right) \\ $$$$\Rightarrow\mathrm{63}{m}+\mathrm{9}{k}.\mathrm{4}^{{k}−\mathrm{1}} \\ $$$$\Rightarrow\mathrm{9}\left(\mathrm{7}{m}+{k}.\mathrm{4}^{{k}−\mathrm{1}} \right)\:{is}\:{divisible}\:{by}\:\mathrm{9}. \\ $$$${q}.{e}.{d}\: \\ $$

Leave a Reply

Your email address will not be published. Required fields are marked *