- #1

- 74

- 0

Show by induction that if N is an odd positive integer then 1+2+3+4+...+(n-1) congruent 0 (mod n)

3. Never done a problem like this before, but I assume after the (n-1) it would be (n-1)+n congruent 0 (mod n+2)

You are using an out of date browser. It may not display this or other websites correctly.

You should upgrade or use an alternative browser.

You should upgrade or use an alternative browser.

- Thread starter Isaak DeMaio
- Start date

- #1

- 74

- 0

Show by induction that if N is an odd positive integer then 1+2+3+4+...+(n-1) congruent 0 (mod n)

3. Never done a problem like this before, but I assume after the (n-1) it would be (n-1)+n congruent 0 (mod n+2)

- #2

SammyS

Staff Emeritus

Science Advisor

Homework Helper

Gold Member

- 11,391

- 1,044

... after the (n-1) it would be n+(n+1) congruent 0 (mod n+2)

Show by induction that if N is an odd positive integer then 1+2+3+4+...+(n-1) congruent 0 (mod n)

3. Never done a problem like this before, but I assume after the (n-1) it would be (n-1)+n congruent 0 (mod n+2)

The following may fit induction better.

Any odd integer may be expressed as 2k+1, where k is an integer. If n = 2k+1, then the next odd integer (greater than n) is given by n+2 = 2(k+1)+1 .

Then n-1 = 2k. So you need to show that 1+2+3+4+...+2k ≡ 0 (mod 2k+1 )

Then n-1 = 2k. So you need to show that 1+2+3+4+...+2k ≡ 0 (mod 2k+1 )

- #3

- 74

- 0

... after the (n-1) it would be n+(n+1) congruent 0 (mod n+2)

So would it be:

0(mod n) + [n+(n+1)] = 0(mod n+2)

if done the way the question presents itself.

- #4

SammyS

Staff Emeritus

Science Advisor

Homework Helper

Gold Member

- 11,391

- 1,044

So would it be:

0(mod n) + [n+(n+1)] = 0(mod n+2)

if done the way the question presents itself.

Yes, for the induction step.

- #5

SammyS

Staff Emeritus

Science Advisor

Homework Helper

Gold Member

- 11,391

- 1,044

Show that 1+2+...+2k = k(2k+1) .

This is equivalent to showing that:

1+2+...+(n‒1) = ((n‒1)/2)(n)

- #6

- 74

- 0

Yes, for the induction step.

How would you cancel out the mods? Or do such things to them to try and make them equivalent?

- #7

Mark44

Mentor

- 35,237

- 7,057

1 + 2 + 3 + ... + (n - 1) [itex]\equiv[/itex] 0 (mod n)

is the same as saying

1 + 2 + 3 + ... + (n - 1) = kn, for some integer k. (It's also given that n is an odd positive integer.)

You can do something similar for the other modulus equation.

- #8

SammyS

Staff Emeritus

Science Advisor

Homework Helper

Gold Member

- 11,391

- 1,044

The idea here is to use the above as a "Lemma". Proving this by induction is a natural thing to do.For n odd, n>0, then n=2k+1 for some k≥0.

Show that 1+2+...+2k = k(2k+1) .

Following whatThis is equivalent to showing that:

1+2+...+(n‒1) = ((n‒1)/2)(n)

Letting m = (n‒1)/2, you then have:

1+2+...+(n‒1) = (m)(n) .

Last edited:

- #9

- 74

- 0

The idea here is to use the above as a "Lemma". Proving this by induction is a natural thing to do.

Following whatMark44said, but using the variable, m, instead of k, which was already used, you have the following

Letting m = (n‒1)/2, you then have:

1+2+...+(n‒1) = (m)(n) .

it has to be in K's

so k-1 = mk

- #10

Mark44

Mentor

- 35,237

- 7,057

No, not at all, if I'm following what you're doing. What I said in my earlier post wasit has to be in K's

so k-1 = mk

if 1 + 2 + 3 + ... + (n - 1) [itex]\equiv[/itex] 0 (mod n),

then 1 + 2 + 3 + ... + (n - 1) = kn for some integer k.

If your first equation is 1 + 2 + 3 + ... + (k - 1) [itex]\equiv[/itex] 0 (mod n), then the second equation is then 1 + 2 + 3 + ... + (k - 1) = mk for some integer m.

It's not true that k - 1 = mk.

- #11

- 74

- 0

i meant (k-1) i just didn't do the parent...

- #12

- 1,086

- 2

The parentheses aren't the issue here, k - 1 is the same as (k - 1).

- #13

- 74

- 0

No, not at all, if I'm following what you're doing. What I said in my earlier post was

if 1 + 2 + 3 + ... + (n - 1) [itex]\equiv[/itex] 0 (mod n),

then 1 + 2 + 3 + ... + (n - 1) = kn for some integer k.

If your first equation is 1 + 2 + 3 + ... + (k - 1) [itex]\equiv[/itex] 0 (mod n), then the second equation is then 1 + 2 + 3 + ... + (k - 1) = mk for some integer m.

It's not true that k - 1 = mk.

Would the set up be...

(mk) + (k-1) = (m)(k-2)? Why why is it minus 1 and not plus one again?

- #14

Mark44

Mentor

- 35,237

- 7,057

Show us your induction proposition and then show is the proposition you need to prove.

- #15

- 74

- 0

Show us your induction proposition and then show is the proposition you need to prove.

I always skip those parts mostly because I don't get those parts.

0(mod n) + [n+(n+1)] = 0(mod n+2)

would that be:

mk + [k+(k+1)] = m(k+2)?

- #16

Mark44

Mentor

- 35,237

- 7,057

That explains why some of your work is so hard to follow. You can't do an induction proof without showing all three steps.I always skip those parts mostly because I don't get those parts.

This makes no sense at all. It is saying that 0 + n + n + 1 = 0; IOW, that 2n + 1 = 0. That's not gonna fly.0(mod n) + [n+(n+1)] = 0(mod n+2)

would that be:

mk + [k+(k+1)] = m(k+2)?

SammyS and I have laid out two slightly different approaches. Go back and read the posts in this thread and pick one of the ways presented, and we can go from there.

- #17

- 74

- 0

Well I don't know what you mean by "the definition of 0 mod n"

But I'll go your way I suppose.

But I'll go your way I suppose.

- #18

Mark44

Mentor

- 35,237

- 7,057

If [itex] x \equiv 0 (\text{mod n})[/itex], that means that x is an integer multiple of n.

- #19

- 74

- 0

If [itex] x \equiv 0 (\text{mod n})[/itex], that means that x is an integer multiple of n.

Ahhh yes. so could you say," K=N" in this proof? well it'd be k greater = n

- #20

Mark44

Mentor

- 35,237

- 7,057

???Ahhh yes. so could you say," K=N" in this proof? well it'd be k greater = n

As I said a few posts back - Show us your induction proposition and then show is the proposition you need to prove.

- #21

- 74

- 0

1+2+3+4+...+(n-1) = (n-1)/2 (n)???

As I said a few posts back - Show us your induction proposition and then show is the proposition you need to prove.

n≥1

1...1=0(mod1).

2...2=0(mod2)

3...3=0(mod3)

4...4=0(mod4)

Prove:1+2+3+4+...+(k-1)+k(k+1) = (k-1+1)/2 (k+1)

k≥1

Would that be it?

- #22

SammyS

Staff Emeritus

Science Advisor

Homework Helper

Gold Member

- 11,391

- 1,044

I second what **Mark44** said.

Added in EDIT:

Ignore this. It was a response to a post a few back.

Added in EDIT:

Ignore this. It was a response to a post a few back.

Last edited:

- #23

- 74

- 0

I second whatMark44said.

didnt i just do that?

- #24

Mark44

Mentor

- 35,237

- 7,057

The general statement:

n is a positive odd integer

Show that 1 + 2 + 3 + ... + (n - 1) [itex]\equiv[/itex] 0 (mod n)

Base case:

1 + 2 = 3 [itex]\equiv[/itex] 0 (mod 3)

This establishes the base case.

Induction step:

Let n = k

Assume that 1 + 2 + 3 + ... + (k - 1) [itex]\equiv[/itex] 0 (mod k) is true. (*)

Now let n = k + 2 (to get to the next odd number)

Show that 1 + 2 + 3 + ... + (k - 1) + k + (k + 1) [itex]\equiv[/itex] 0 (mod k + 2). Use (*) in showing this.

Note that the sum on the left starts at 1 and ends at some even number, so in the induction step, you need to add on two more numbers.

n is a positive odd integer

Show that 1 + 2 + 3 + ... + (n - 1) [itex]\equiv[/itex] 0 (mod n)

Base case:

1 + 2 = 3 [itex]\equiv[/itex] 0 (mod 3)

This establishes the base case.

Induction step:

Let n = k

Assume that 1 + 2 + 3 + ... + (k - 1) [itex]\equiv[/itex] 0 (mod k) is true. (*)

Now let n = k + 2 (to get to the next odd number)

Show that 1 + 2 + 3 + ... + (k - 1) + k + (k + 1) [itex]\equiv[/itex] 0 (mod k + 2). Use (*) in showing this.

Note that the sum on the left starts at 1 and ends at some even number, so in the induction step, you need to add on two more numbers.

Last edited:

- #25

Mark44

Mentor

- 35,237

- 7,057

This is true, but I don't see how it is related to this problem.1+2+3+4+...+(n-1) = (n-1)/2 (n)

These don't make any sense. In each of the equations above, the left side apparently consists of a single number. That's not what this problem is about.n≥1

1...1=0(mod1).

2...2=0(mod2)

3...3=0(mod3)

4...4=0(mod4)

Equations that are pertinent include the following:

1 + 2 = 3 [itex]\equiv[/itex] 0 (mod 3)

1 + 2 + 3 + 4 = 10 [itex]\equiv[/itex] 0 (mod 5)

1 + 2 + 3 + 4 + 5 + 6 = 21 [itex]\equiv[/itex] 0 (mod 7)

Any one of these establishes a base case, but they don't do anything for establishing the induction step.

Prove:1+2+3+4+...+(k-1)+k(k+1) = (k-1+1)/2 (k+1)

k≥1

Would that be it?

Share: