Is 1+2+3+4+...+(n-1) divisible by N (odd positive integer)?

[Isaak DeMaio]

1. This is an extra credit question for me, we haven't gone over this at all.
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)

 

[SammyS]

1. This is an extra credit question for me, we haven't gone over this at all.
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)

... after the (n-1) it would be n+(n+1) 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 )​

 

[Isaak DeMaio]

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

 

[SammyS]

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.

 

[SammyS]

For n odd, n>0, then n=2k+1 for some k≥0.

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

This is equivalent to showing that:

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

 

[Isaak DeMaio]

Yes, for the induction step.

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

 

[Mark44]

You can get rid of the modulus business by using the definition of 0 (mod n). For example, the equation
1 + 2 + 3 + ... + (n - 1) \equiv 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.

 

[SammyS]

For n odd, n>0, then n=2k+1 for some k≥0.

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

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

This is equivalent to showing that:

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

Following what Mark44 said, 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) .

 

[Isaak DeMaio]

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


Following what Mark44 said, 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

 

[Mark44]

it has to be in K's
so k-1 = mk

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) \equiv 0 (mod n),
then 1 + 2 + 3 + ... + (n - 1) = kn for some integer k.

If your first equation is 1 + 2 + 3 + ... + (k - 1) \equiv 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.

 

[Isaak DeMaio]

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

 

[Ryker]

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

 

[Isaak DeMaio]

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) \equiv 0 (mod n),
then 1 + 2 + 3 + ... + (n - 1) = kn for some integer k.

If your first equation is 1 + 2 + 3 + ... + (k - 1) \equiv 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?

 

[Mark44]

You're skipping too many steps for me to follow easily.

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

 

[Isaak DeMaio]

You're skipping too many steps for me to follow easily.

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

 

[Mark44]

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

That explains why some of your work is so hard to follow. You can't do an induction proof without showing all three steps.

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

This makes no sense at all. It is saying that 0 + n + n + 1 = 0; IOW, that 2n + 1 = 0. That's not going to fly.

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.

 

[Isaak DeMaio]

Well I don't know what you mean by "the definition of 0 mod n"
But I'll go your way I suppose.

 

[Mark44]

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

 

[Isaak DeMaio]

If x \equiv 0 (\text{mod n}), 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

 

[Mark44]

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.

 

[Isaak DeMaio]

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

1+2+3+4+...+(n-1) = (n-1)/2 (n)
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?

 

[SammyS]

I second what Mark44 said.

Added in EDIT:

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

 

[Isaak DeMaio]

I second what Mark44 said.

didnt i just do that?

 

[Mark44]

The general statement:
n is a positive odd integer
Show that 1 + 2 + 3 + ... + (n - 1) \equiv 0 (mod n)

Base case:
1 + 2 = 3 \equiv 0 (mod 3)
This establishes the base case.

Induction step:
Let n = k
Assume that 1 + 2 + 3 + ... + (k - 1) \equiv 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) \equiv 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.

 

[Mark44]

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

This is true, but I don't see how it is related to this problem.

n≥1
1...1=0(mod1).
2...2=0(mod2)
3...3=0(mod3)
4...4=0(mod4)

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.

Equations that are pertinent include the following:
1 + 2 = 3 \equiv 0 (mod 3)
1 + 2 + 3 + 4 = 10 \equiv 0 (mod 5)
1 + 2 + 3 + 4 + 5 + 6 = 21 \equiv 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?

 

[SammyS]

...

Now let n = k + 1 (to get to the next even number)
...

Show that 1 + 2 + 3 + ... + (k - 1) + k + (k + 1) \equiv 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.

Pardon me for butting in, but I'm sure the line I highlighted should say:

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

The line following that is fine.

 

[SammyS]

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

This is true, but I don't see how it is related to this problem.
...

At Mark44;
That came from me, in post #5.

The idea here is that this can be proved by induction and that clearly: ((n-1)/2)(n) ≡ 0 (mod n)

 

[Mark44]

Pardon me for butting in, but I'm sure the line I highlighted should say:

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

The line following that is fine.

No problem, and thanks. I edited that post to reflect the change. I was thinking about the last number in the sum, which has to be even, when I wrote that.

 

[Isaak DeMaio]

No problem, and thanks. I edited that post to reflect the change. I was thinking about the last number in the sum, which has to be even, when I wrote that.

So I should follow this:

The general statement:
n is a positive odd integer
Show that 1 + 2 + 3 + ... + (n - 1) 0 (mod n)

Base case:
1 + 2 = 3 0 (mod 3)
This establishes the base case.

Induction step:
Let n = k
Assume that 1 + 2 + 3 + ... + (k - 1) 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) 0 (mod k + 2).

Then try and prove it to get the correct answer?

 

[Isaak DeMaio]

So it would be 3k=0(mod k+2)

Could you subtract the K over to get 2k=0(mod2)?
then would that be it?