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.


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

$B y s t r o n g i n d u c t i o n p r o v e t h a t a n y$ $n a t u r a l n u m b e r e q u a l t o o r b i g g e r t h a n$ $8 c a n b e w r i t t e n a s 3 a + 5 b w h e r e a a n d b$ $a r e n o n - n e g a t i v e i n t e g e r s .$
	Answered by des_ last updated on 12/Nov/23

	$n ⩾ 8 \Rightarrow n = 3 a + 5 b, a, b ⩾ 0;$ $1) n = 8 :$ $n = 3 (1) + 5 (1)$ $2) n \Rightarrow n + 1 :$ $2.1) n = 3 a + 5 b, b > 0 :$ $n + 1 = 3 a + 5 b + 1 = 3 (a + 2) + 5 (b - 1);$ $2.2) n = 3 a + 5 b, b = 0 :$ $n = 3 a \Rightarrow a ⩾ 3;$ $n + 1 = 3 a + 1 = 3 (a - 3) + 5 (2);$ $T h u s n ⩾ 8 \Rightarrow n = 3 a + 5 b, a, b ⩾ 0$
	Answered by witcher3 last updated on 12/Nov/23

	$show for n \in [8, 16] . . By tcheking$ $for all 16 ⩽ k ⩽ n \Rightarrow P (k) True$ $p (n + 1)$ $n + 1 = {[\frac{n + 1}{2}]}_{m} + {(n - [\frac{n + 1}{2}])}_{= d}$ $8 ⩽ m, d < n$ $m = 3 a + 5 d$ $d = {3 a}^{'} + {5 d}^{'}$ $m + d = n = 3 (a + a^{'}) + 5 (d + d^{'})$
	Answered by witcher3 last updated on 12/Nov/23

	$we can show this easly$ $n = 8 k + 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)$ $\forall r \in [0, 7]$ $r = 3 . a + b . 5 \min (a, b) ⩾ - 1$ $n = k (3 + 5) + 3 a + 5 b = 3 (a + k) + 5 (k + b)$ $a + k ⩾ k - 1 ⩾ 0$ $b + k ⩾ k - 1 ⩾ 0 . . True$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum