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 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

Facebook Tweet Pin