Proof by Induction - Proving divisibility

Hi guys,
I'm struggling a little bit understand how to prove, by induction, that something is divisible by

x

The question I'm having trouble is:

Prove by induction that, for all positive integers n,

2^{3n}-1

is divisible exactly by

7

Spoiler

Any help is greatly appreciated
Thanks in advance

Reply 1

Farhan.Hanif93

Original post by chapmouse

Hi guys,
I'm struggling a little bit understand how to prove, by induction, that something is divisible by

x

The question I'm having trouble is:

Prove by induction that, for all positive integers n,

2^{3n}-1

is divisible exactly by

7

Spoiler

Any help is greatly appreciated
Thanks in advance

Consider

(2^{3(k+1)}-1) - (2^{3k} -1)

. If you can show this is divisible by 7, you're done. (why?)

Reply 2

Phichi

Original post by chapmouse

Hi guys,
I'm struggling a little bit understand how to prove, by induction, that something is divisible by

x

The question I'm having trouble is:

Prove by induction that, for all positive integers n,

2^{3n}-1

is divisible exactly by

7

Spoiler

Any help is greatly appreciated
Thanks in advance

The whole reason you test values for n=1, n=2, or w/e, depending on the question, is just to check that it holds for 'any value of n'. Thus we can ASSUME its also true for n=k, and n=k+1, and so on. So you dont need to prove its true for n=k+1, we are already assuming it is. So like Farhan said;

(2^{3(k+1)}-1)

by subbing n=k+1 in.

The next step to proving divisiblity, is showing that

(n=k+1)-(n=k)

is divisible by 7, so take Farhan's equation and work with it:

(2^{3(k+1)}-1) - (2^{3k} -1)

Remember, we are assuming n=k is divisible by 7, and we are also assuming n=k+1 is, so the difference between them must also be divisible by 7, that is what we are showing. Eg, 49-7=42. 42/7=6.

Reply 3

chapmouse

Original post by Farhan.Hanif93

Consider

(2^{3(k+1)}-1) - (2^{3k} -1)

. If you can show this is divisible by 7, you're done. (why?)

Why are you subtracting? I thought I had to add the

n=1

term to the

n=k

term, both of which I already had?

Reply 4

Phichi

Original post by chapmouse

Why are you subtracting? I thought I had to add the

n=1

term to the

n=k

term, both of which I already had?

f(k+1)\neq f(k)+f(1)

Check my post.

(edited 10 years ago)

Reply 5

chapmouse

Original post by Phichi

f(k+1)\neq f(k)+f(1)

Check my post.

I don't understand why this is true. I have been taught to assume true for

n=k

and prove that

n=k+1

works. It works with sequences, series, and matrices proofs. I'm doing this question from a specimen paper, where the proof questions aren't provided with a solution, which is the only thing i'm struggling with...

Reply 6

Felix Felicis

Original post by chapmouse

I don't understand why this is true. I have been taught to assume true for

n=k

and prove that

n=k+1

Say if you have a function f(x). If f(x) is divisible by 7 for some x (just because it's from your question, it could be any number, say, p) and the difference between successive values i.e. f(x+1) - f(x) is also divisible by 7 (or p) then f(x) is divisible by 7 for all x

(edited 10 years ago)

Reply 7

Phichi

Original post by chapmouse

I don't understand why this is true. I have been taught to assume true for

n=k

and prove that

n=k+1

Because its hard for re-arrange n=k+1, to show its divisible by 7. Thus you use the method of n=k+1 - n=k, to show that the difference is divisible by 7, its just procedure.

(edited 10 years ago)

Reply 8

Joshmeid

Original post by chapmouse

I don't understand why this is true. I have been taught to assume true for

n=k

and prove that

n=k+1

Consider the function

f(x) = x^{2}

f(k + 1) = (k + 1)^{2}

f(k) = k^{2}

f(1) = 1^{2} = 1

I hope you can see that

(k + 1)^{2} \not= k^{2} + 1

.

Hence

f(k + 1) \not= f(k) + f(1)

Reply 9

chapmouse

Original post by Joshmeid

Consider the function

f(x) = x^{2}

f(k + 1) = (k + 1)^{2}

f(k) = k^{2}

f(1) = 1^{2} = 1

I hope you can see that

(k + 1)^{2} \not= k^{2} + 1

.

Hence

f(k + 1) \not= f(k) + f(1)

but is

f(k) = f(k+1) - f(1)

Reply 10

Joshmeid

Original post by chapmouse

but is

f(k) = f(k+1) - f(1)

f(k) = k^{2}

f(k + 1) - f(1)

= (k + 1)^{2} - 1^{2}

= k^{2} + 2k \not= k^{2}

(edited 10 years ago)

Reply 11

Phichi

Original post by chapmouse

but is

f(k) = f(k+1) - f(1)

That is the same as implying

f(k) +f(1) = f(k+1)

Reply 12

Felix Felicis

Original post by chapmouse

but is

f(k) = f(k+1) - f(1)

f(k) is the expression you want to prove the proposition for in the question taking the value for some arbitrary integer k. Same goes for f(k+1) - check my last post, if you can show f(k+1) - f(k) is divisible by 7, then combined with your basis case, you're done

Reply 13

Phichi

You need to understand, the x values you are subbing in, are not the values of your function. Sure if f(x)=x then f(k)+f(1)=f(k+1), but in any other case it doesn't, unless unique.

Reply 14

Phichi

Original post by Phichi

(2^{3(k+1)}-1)

by subbing n=k+1 in.

The next step to proving divisiblity, is showing that

(n=k+1)-(n=k)

is divisible by 7, so take Farhan's equation and work with it:

(2^{3(k+1)}-1) - (2^{3k} -1)

Remember, we are assuming n=k is divisible by 7, and we are also assuming n=k+1 is, so the difference between them must also be divisible by 7, that is what we are showing. Eg, 49-7=42. 42/7=6.

Just follow this method, that I described before, for all divisibility questions, and you'll be fine. If you need help on the algebra, just ask.

f(k+1)-f(k), and prove its divisible by 7.