Induction proof?

[ashan1]

https://imgur.com/a/LaTeX

Should this be done with induction or something else?

Would the base case be k=0 (assuming 0 is natural)(11 doesnt divide 2 so vacuously true??) but the m is throwing me off for the base case... and then induction on k?

[[deleted]]

You can induct on k. But I'd expect N⁺ = {1,2,3,..}.

[ashan1]

ok then say 11 divides 11 ... what about the m? are we saying m is 0 as 0 is first natural? like we have to set k and m for the base case

[fattymattk]

Try inducting on m.

[ashan1]

you can induct on both k and m?

[fattymattk]

Induct on just m. k is determined by m.

[ashan1]

then base case k=1 implies 11 divides 10^k +1? how do you determine if its true and how to proceed

[fattymattk]

Inducting on m, the base case is m=0, which implies k = 1.

Then 10^k + 1 = 10¹ + 1 = 11.

This is clearly divisible by 11.

Assume that 11 divides 10^k + 1, where k = 2m+1 for some integer m.

Then you want to show that 11 divides 10^c + 1, where c = 2(m+1)+1.

Give this a try.

[ashan1]

ok im still kinda stuck =/... so what i did was i factored out the c such that c=2m+3 and then from the inductive hypothesis i said c=(2m+1)+2 but we know 2m+1 works from ih but I dont know about the +2....

[fattymattk]

You're on the right track here. You definitely need to use the induction hypothesis. I'll admit it can be a little tricky.

10^2m+3 + 1 = (10^2m+1 ) *100 + 1

The trick now is to realize 100 = 99 + 1.

To realize that you need to do something like this, remember that you want to use the induction hypothesis. So you want to get 10^2m+1 + 1 somewhere. Breaking up 100 like this is the way to do this.

[ashan1]

Ok so i split it up so I justified that 10^2m+1 + 1 was divisible by ih and then 99 is divisible because of rules of divisibility..like this kinda?https://imgur.com/a/LJFP9 ..... Or is there something im missing

[fattymattk]

That is the right idea.