Proof that every number ≥ 88 can be represented by a sum of fives and threes.

Can you check if my proof is right?

Theorem. x8,x can be represented by 5a+3b where a,bN.

Base case(s): x=8=31+51x=9=33+50x=10=30+52

Inductive step:

nNa1=8,an=a1+(x1)3b1=9,bn=b1+(x1)3=a1+1+(x1)3c1=10,cn=c1+(x1)3=b1+1+(x1)3=a1+2+(x1)3S={xN:xaxxbxxcx}

Basis stays true, because 8,9,10S

Lets assume that xS. That means xanxbnxcn.

If xan then x+1bx,

If xbx then x+1cx,

If xcx then x+1ax.

I can’t prove that but it’s obvious. What do you think about this?

Answer

Proof by induction.
For the base case n=8 we have 8=5+3.
Suppose that the statement holds for k where k>8. We show that it holds for k+1.

There are two cases.

1) k has a 5 as a summand in its representation.

2) k has no 5 as a summand in its representation.

For case 1, we delete “that 5” in the sum representation of k and replace it by two “3“s ! This proves the statement for k+1.

For case 2, since k>8, then k has at least three “3“s in its sum representation. We remove these three 3‘s and replace them by two fives! We obtain a sum representation for k+1. This completes the proof.

Attribution
Source : Link , Question Author : 88sandvich , Answer Author : Fermat

Leave a Comment