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

[Mark44]

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

No. Where are you getting that?

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

No, it doesn't work that way.

Start with 1 + 2 + 3 + ... + (k - 1) + k + (k + 1).
Use what you know (have assumed) about 1 + 2 + 3 + ... + (k - 1), to show that the expression above is congruent to 0 (mod k + 2).

 

[Isaak DeMaio]

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?

Would it be:

0 (mod k) + k + (k+1) = 0 (mod k + 2)

Then:

0(mod k) + 2k + 1 = 0 (mod k+2)

 

[Mark44]

Would it be:

0 (mod k) + k + (k+1) = 0 (mod k + 2)

Then:

0(mod k) + 2k + 1 = 0 (mod k+2)

They are both equivalent, but you need to establish that these equations are true, not just write them down. Again, start with 1 + 2 + 3 + ... + (k - 1) + k + (k + 1). By that, I mean that this should be the first thing you write down. Then write an =. Then use what you know (have assumed) about 1 + 2 + 3 + ... + (k - 1), to show that the expression above is congruent to 0 (mod k + 2).

 

[SammyS]

Would it be:

0 (mod k) + k + (k+1) = 0 (mod k + 2)

Then:

0(mod k) + 2k + 1 = 0 (mod k+2)

Isaak DeMaio,

It appears that you continue to be confused by modular arithmetic --- or at least by the notation.

For this problem the context is:

The statement "a ≡ b (mod c)" is read as "a is congruent to b mod c."
It means that there is an integer, k, such that a ‒ b = k·c​

On the other hand:
"mod" may also be used in the context of a mathematical operation.

Sometimes it is written as (27 mod 7) other times: mod(27, 7). In either case the result is 6. It's basically the remainder when doing division (in this case 27÷7), especially with integers.​

So, when you write:

0 (mod k) + k + (k+1) = 0 (mod k + 2),
it's not clear what you mean.
0 (mod k) is (congruent to) zero.
You're left with: k + (k+1) = 0 (mod k + 2)

Do you mean: k + (k+1) is congruent to 0 mod(k+2) .
or --- since 0 (mod k + 2) =0, as a mathematical operation,
Do you mean: k + (k+1) = 0 ?​

 

[Isaak DeMaio]

well would it be 2k+1 = 0 mod(k+2)
I don't know what I mean, which is why I asked the question. I've never done a induction proof with mod before.

 

[Mark44]

Here's what I said in post #33. Did you see it?

Again, start with 1 + 2 + 3 + ... + (k - 1) + k + (k + 1). By that, I mean that this should be the first thing you write down. Then write an =. Then use what you know (have assumed) about 1 + 2 + 3 + ... + (k - 1), to show that the expression above is congruent to 0 (mod k + 2).​

Instead at continuing to guess at things you think might be the key to this problem (they aren't), follow the steps in the paragraph above.

 

[Isaak DeMaio]

that is the first thing I wrote down...

1 + 2 + 3 + ... + (k - 1) + k + (k + 1)

=

don't i know that 0 (mod k+2) will be equal to that?

 

[Mark44]

that is the first thing I wrote down...

But you didn't write it in your posts, and that is what I was asking for.

1 + 2 + 3 + ... + (k - 1) + k + (k + 1)

=


don't i know that 0 (mod k+2) will be equal to that?

And that's what you have to prove.

In the equation above, you can replace all but the last two terms with something. So you will have

1 + 2 + 3 + ... + (k - 1) + k + (k + 1)
= <something> + k + (k + 1)

What can you put in place of <something> above?

 

[Isaak DeMaio]

But you didn't write it in your posts, and that is what I was asking for.

And that's what you have to prove.

In the equation above, you can replace all but the last two terms with something. So you will have

1 + 2 + 3 + ... + (k - 1) + k + (k + 1)
= <something> + k + (k + 1)

What can you put in place of <something> above?

0 (mod k +2)?

 

[Mark44]

No.

What do you know about 1 + 2 + 3 + ... + (k - 1)?

 

[Isaak DeMaio]

2k+1 comes after it.

 

[Mark44]

Presumably you've done at least one other proof by induction. If so, you have made an assumption about the value of 1 + 2 + 3 + ... + (k - 1). That value is what you replace this expression by.

 

[Mark44]

Here's a link to a wiki page on mathematical induction - http://en.wikipedia.org/wiki/Mathematical_induction

There's an example that might help you out.

 

[Isaak DeMaio]

and every other time I done it how I am saying but apparently I've been doing it wrong and getting the right answer.

 

[Isaak DeMaio]

that's what I have been saying is it not?

 

[Isaak DeMaio]

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

0 (mod k) + 2k+1 = 0 (mod k+2)

 

[Mark44]

and every other time I done it how I am saying but apparently I've been doing it wrong and getting the right answer.

There isn't a "right answer" like x = 3 when you do a proof.

 

[Isaak DeMaio]

There isn't a "right answer" like x = 3 when you do a proof.

I know Sherlock.

 

[Mark44]

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

0 (mod k) + 2k+1 = 0 (mod k+2)

From the induction hypothesis, you have assumed that 1 + 2 + 3 + ... + (k - 1) \equiv 0 (mod k).

What does that say about 1 + 2 + 3 + ... + (k - 1) if its remainder when you divide by k is 0?

 

[Isaak DeMaio]

k=0 (mod k)

 

[Mark44]

That's trivially true and irrelevant.

In different words, and without using mod, modulo, etc, what does this equation, 1 + 2 + 3 + ... + (k - 1) \equiv
0 (mod k) mean?

 

[Isaak DeMaio]

they're congruent.

 

[Mark44]

You are using "mod" by implication when you say congruent.

Another tack: what is 1 + 2 + 3 + ... + (k - 1) equal to? I'm am NOT asking what it's congruent to. I already know the answer to that.

 

[Robert1986]

As a side note, do you HAVE to prove by induction? Or did your instructor just mention this as a possible mode of attack?

 

[Dick]

You are using "mod" by implication when you say congruent.

Another tack: what is 1 + 2 + 3 + ... + (k - 1) equal to? I'm am NOT asking what it's congruent to. I already know the answer to that.

Right. This has probably already been said several times at some point in this endless thread. But attacking this problem directly by induction is a mess. Proving 1+2+3+...+k=k*(k+1)/2 is easy to prove by induction. Now forget the induction, you already used it. Now attack the problem using that. We all knew this, right? Maybe best to say so in so many words.

 

[Isaak DeMaio]

Yes by Induction Robert.

Why can't you just tell me?

 

[Robert1986]

Yes by Induction Robert.

Why can't you just tell me?

Why can't I just tell you
1) It is against PF rules.
2) I don't want to.
3) You seem completely unwilling to learn what modular arithmetic is
4) and this is most important, I haven't figured out how to do this via induction. And you know what? I'm not going to, either. Mark44 and SammyS seem to have worked it out, so I would just follow his advice.


The only "inductive" proof I can think of is using induction to prove what 1+2+...+(k-1) is equal to. Then showing that k divides 1 + 2 + ... + (k-1), which is what the previous poster suggested doing, and if I was turning this assignment in, I would do exactly that.


You said in another thread that this is for a number theory class; I was wondering, what is your major? Is it CS, by any chance?

 

[Robert1986]

Right. This has probably already been said several times at some point in this endless thread. But attacking this problem directly by induction is a mess. Proving 1+2+3+...+k=k*(k+1)/2 is easy to prove by induction. Now forget the induction, you already used it. Now attack the problem using that. We all knew this, right? Maybe best to say so in so many words.

That is what I did, though I didn't use induction to prove 1+2+3+...+k=k*(k+1)/2, I just sort of took that for granted. Then it is pretty easy to show what you need to show. But, it seems that Mark44 has done this using a direct inductive argument, is that correct Mark44? I haven't come up with one, but I haven't really given it much thought and I doubt I will.

 

[Isaak DeMaio]

Why can't I just tell you
1) It is against PF rules.
2) I don't want to.
3) You seem completely unwilling to learn what modular arithmetic is
4) and this is most important, I haven't figured out how to do this via induction. And you know what? I'm not going to, either. Mark44 and SammyS seem to have worked it out, so I would just follow his advice.


The only "inductive" proof I can think of is using induction to prove what 1+2+...+(k-1) is equal to. Then showing that k divides 1 + 2 + ... + (k-1), which is what the previous poster suggested doing, and if I was turning this assignment in, I would do exactly that.


You said in another thread that this is for a number theory class; I was wondering, what is your major? Is it CS, by any chance?

Not the answer just what the hell I am not understanding. Why would you divide it all by K, that makes no sense at all.

Math Education

 

[Robert1986]

Not the answer just what the hell I am not understanding. Why would you divide it all by K, that makes no sense at all.

Math Education

Ok, nothing is being divided by K, I'm not sure what you are referring to, perhaps I made a typo somewhere.

if 1 + 2 + ... + k = k(k+1)/2, what can you conclude?