Question and Answers Forum

All Questions      Topic List

Number Theory Questions

Previous in All Question      Next in All Question      

Previous in Number Theory      Next in Number Theory      

Question Number 200041 by depressiveshrek last updated on 12/Nov/23

By strong induction prove that any natural number equal to or bigger than 8 can be written as 3a+5b where a and b are non−negative integers.

$${By}\:{strong}\:{induction}\:{prove}\:{that}\:{any} \\ $$$${natural}\:{number}\:{equal}\:{to}\:{or}\:{bigger}\:{than} \\ $$$$\mathrm{8}\:{can}\:{be}\:{written}\:{as}\:\mathrm{3}{a}+\mathrm{5}{b}\:{where}\:{a}\:{and}\:{b} \\ $$$${are}\:{non}−{negative}\:{integers}. \\ $$

Answered by des_ last updated on 12/Nov/23

n ≥ 8 ⇒ n = 3a + 5b, a,b ≥ 0; 1) n = 8: n = 3(1) + 5(1) 2) n ⇒ n + 1: 2.1) n = 3a + 5b, b > 0: n + 1 = 3a + 5b + 1 = 3(a + 2) + 5(b − 1); 2.2) n = 3a + 5b, b = 0: n = 3a ⇒ a ≥ 3; n + 1 = 3a + 1 = 3(a − 3) + 5(2); Thus n ≥ 8 ⇒ n = 3a + 5b, a,b ≥ 0

$${n}\:\geqslant\:\mathrm{8}\:\Rightarrow\:{n}\:=\:\mathrm{3}{a}\:+\:\mathrm{5}{b},\:{a},{b}\:\geqslant\:\mathrm{0}; \\ $$$$ \\ $$$$\left.\mathrm{1}\right)\:{n}\:=\:\mathrm{8}: \\ $$$${n}\:=\:\mathrm{3}\left(\mathrm{1}\right)\:+\:\mathrm{5}\left(\mathrm{1}\right) \\ $$$$ \\ $$$$\left.\mathrm{2}\right)\:{n}\:\Rightarrow\:{n}\:+\:\mathrm{1}: \\ $$$$\left.\mathrm{2}.\mathrm{1}\right)\:{n}\:=\:\mathrm{3}{a}\:+\:\mathrm{5}{b},\:{b}\:>\:\mathrm{0}: \\ $$$${n}\:+\:\mathrm{1}\:=\:\mathrm{3}{a}\:+\:\mathrm{5}{b}\:+\:\mathrm{1}\:=\:\mathrm{3}\left({a}\:+\:\mathrm{2}\right)\:+\:\mathrm{5}\left({b}\:−\:\mathrm{1}\right); \\ $$$$\left.\mathrm{2}.\mathrm{2}\right)\:{n}\:=\:\mathrm{3}{a}\:+\:\mathrm{5}{b},\:{b}\:=\:\mathrm{0}: \\ $$$${n}\:=\:\mathrm{3}{a}\:\Rightarrow\:{a}\:\geqslant\:\mathrm{3}; \\ $$$${n}\:+\:\mathrm{1}\:=\:\mathrm{3}{a}\:+\:\mathrm{1}\:=\:\mathrm{3}\left({a}\:−\:\mathrm{3}\right)\:+\:\mathrm{5}\left(\mathrm{2}\right); \\ $$$$ \\ $$$${Thus}\:{n}\:\geqslant\:\mathrm{8}\:\Rightarrow\:{n}\:=\:\mathrm{3}{a}\:+\:\mathrm{5}{b},\:{a},{b}\:\geqslant\:\mathrm{0} \\ $$

Answered by witcher3 last updated on 12/Nov/23

show for n∈[8,16]..By tcheking for all 16≤k≤n ⇒P(k) True p(n+1) n+1=[((n+1)/2)]_m +(n−[((n+1)/2)])_(=d) 8≤m,d<n m=3a+5d d=3a′+5d′ m+d=n=3(a+a′)+5(d+d′)

$$\mathrm{show}\:\mathrm{for}\:\mathrm{n}\in\left[\mathrm{8},\mathrm{16}\right]..\mathrm{By}\:\mathrm{tcheking} \\ $$$$\mathrm{for}\:\mathrm{all}\:\:\mathrm{16}\leqslant\mathrm{k}\leqslant\mathrm{n}\:\:\Rightarrow\mathrm{P}\left(\mathrm{k}\right)\:\mathrm{True} \\ $$$$\mathrm{p}\left(\mathrm{n}+\mathrm{1}\right) \\ $$$$\mathrm{n}+\mathrm{1}=\left[\frac{\mathrm{n}+\mathrm{1}}{\mathrm{2}}\right]_{\mathrm{m}} +\left(\mathrm{n}−\left[\frac{\mathrm{n}+\mathrm{1}}{\mathrm{2}}\right]\right)_{=\mathrm{d}} \\ $$$$\mathrm{8}\leqslant\mathrm{m},\mathrm{d}<\mathrm{n} \\ $$$$\mathrm{m}=\mathrm{3a}+\mathrm{5d} \\ $$$$\mathrm{d}=\mathrm{3a}'+\mathrm{5d}' \\ $$$$\mathrm{m}+\mathrm{d}=\mathrm{n}=\mathrm{3}\left(\mathrm{a}+\mathrm{a}'\right)+\mathrm{5}\left(\mathrm{d}+\mathrm{d}'\right) \\ $$$$ \\ $$$$ \\ $$

Answered by witcher3 last updated on 12/Nov/23

we can show this easly n=8k+r k≥1 for n≥8 r=0,3.0+5.0 r=1=3.2+5(−1) r=2 5.1+3(−1) r=3=3.0 r=4=3.3+5(−1) r=5=5.1+3.0 r=6,3.2+5(0) r=7,5.2+3(−1) ∀r∈[0,7] r=3.a+b.5 min(a,b)≥−1 n=k(3+5)+3a+5b=3(a+k)+5(k+b) a+k≥k−1≥0 b+k≥k−1≥0..True

$$\mathrm{we}\:\mathrm{can}\:\mathrm{show}\:\mathrm{this}\:\mathrm{easly} \\ $$$$\mathrm{n}=\mathrm{8k}+\mathrm{r} \\ $$$$\mathrm{k}\geqslant\mathrm{1}\:\mathrm{for}\:\mathrm{n}\geqslant\mathrm{8} \\ $$$$\mathrm{r}=\mathrm{0},\mathrm{3}.\mathrm{0}+\mathrm{5}.\mathrm{0} \\ $$$$\mathrm{r}=\mathrm{1}=\mathrm{3}.\mathrm{2}+\mathrm{5}\left(−\mathrm{1}\right) \\ $$$$\mathrm{r}=\mathrm{2}\:\mathrm{5}.\mathrm{1}+\mathrm{3}\left(−\mathrm{1}\right) \\ $$$$\mathrm{r}=\mathrm{3}=\mathrm{3}.\mathrm{0} \\ $$$$\mathrm{r}=\mathrm{4}=\mathrm{3}.\mathrm{3}+\mathrm{5}\left(−\mathrm{1}\right) \\ $$$$\mathrm{r}=\mathrm{5}=\mathrm{5}.\mathrm{1}+\mathrm{3}.\mathrm{0} \\ $$$$\mathrm{r}=\mathrm{6},\mathrm{3}.\mathrm{2}+\mathrm{5}\left(\mathrm{0}\right) \\ $$$$\mathrm{r}=\mathrm{7},\mathrm{5}.\mathrm{2}+\mathrm{3}\left(−\mathrm{1}\right) \\ $$$$\forall\mathrm{r}\in\left[\mathrm{0},\mathrm{7}\right] \\ $$$$\mathrm{r}=\mathrm{3}.\mathrm{a}+\mathrm{b}.\mathrm{5}\:\:\:\mathrm{min}\left(\mathrm{a},\mathrm{b}\right)\geqslant−\mathrm{1} \\ $$$$\mathrm{n}=\mathrm{k}\left(\mathrm{3}+\mathrm{5}\right)+\mathrm{3a}+\mathrm{5b}=\mathrm{3}\left(\mathrm{a}+\mathrm{k}\right)+\mathrm{5}\left(\mathrm{k}+\mathrm{b}\right) \\ $$$$\mathrm{a}+\mathrm{k}\geqslant\mathrm{k}−\mathrm{1}\geqslant\mathrm{0} \\ $$$$\mathrm{b}+\mathrm{k}\geqslant\mathrm{k}−\mathrm{1}\geqslant\mathrm{0}..\mathrm{True} \\ $$$$ \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com