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

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

 

[Isaak DeMaio]

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.

where do you get this divided by 2 from?

 

[Isaak DeMaio]

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?

I don't understand where you are getting a 2 from.

 

[Isaak DeMaio]

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

Where do you go a denominator of 2 for any of this?

 

[Robert1986]

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

Where do you go a denominator of 2 for any of this?

So, here is how I would prove this, which I think departs slightly from what Mark44 was doing:

1)For any integer k, 1+2+...+k=k(k+1)/2, prove this using induction. If you have proven things via induction as you say you have, this is a piece of cake.

2)Use this to conclude that if k+1 is odd, then 1+2+...+k is divisible by k+1, that is 1+2+...+k = 0 (mod k+1)

I've just about spelled it out as clearly as I can without giving you the answer, go for it, and don't respond for at least half an hour; think about it before responding.

 

[Isaak DeMaio]

So, here is how I would prove this, which I think departs slightly from what Mark44 was doing:

1)For any integer k, 1+2+...+k=k(k+1)/2, prove this using induction. If you have proven things via induction as you say you have, this is a piece of cake.

2)Use this to conclude that if k+1 is odd, then 1+2+...+k is divisible by k+1, that is 1+2+...+k = 0 (mod k+1)

I've just about spelled it out as clearly as I can without giving you the answer, go for it, and don't respond for at least half an hour; think about it before responding.

Say this again but in induction form so I can understand it.

 

[Robert1986]

Say this again but in induction form so I can understand it.

No. You didn't even wait ten minutes. Did you think about it? Look, if you expect to do well in Math, you can't expect that you will always have someone over your shoulder telling you what to do next. I am not going to write this in "induction form", but I will reiterate what I said before:

1)Prove that for any integer k, 1+2+...+k = k(k+1)/2. You have said that you can do inductive proofs, this is a rather basic inductive proof, in fact, it is the most basic inductive proof I can think of. If you can do induction, you can do this. And I am not going to tell you how to use induction, you are going to have to figure that out own your own. Spend a little time, put some effort into it.

2)So now that you know that 1+2+...+k=k(k+1)/2 what can you conclude? This part involves NO INDUCTION AT ALL. Think about these things: Is k even or odd? Is k+1 even or odd? Is k/2 an integer? Is (k+1)/2 an integer? How do the answers to these questions relate to what I am trying to prove?


Now, spend some time on this. You are giving up way too easily. Like I said, if you want to be successful at math, whether you are doing research, working in some applied area or teaching, you are going to have to figure stuff out for yourself. We have given you ample "hints" (we have, in fact, done much more than that), if you refuse to think about it, there really isn't a lot more that we can do.

 

[Isaak DeMaio]

No. You didn't even wait ten minutes. Did you think about it? Look, if you expect to do well in Math, you can't expect that you will always have someone over your shoulder telling you what to do next. I am not going to write this in "induction form", but I will reiterate what I said before:

1)Prove that for any integer k, 1+2+...+k = k(k+1)/2. You have said that you can do inductive proofs, this is a rather basic inductive proof, in fact, it is the most basic inductive proof I can think of. If you can do induction, you can do this. And I am not going to tell you how to use induction, you are going to have to figure that out own your own. Spend a little time, put some effort into it.

2)So now that you know that 1+2+...+k=k(k+1)/2 what can you conclude? This part involves NO INDUCTION AT ALL. Think about these things: Is k even or odd? Is k+1 even or odd? Is k/2 an integer? Is (k+1)/2 an integer? How do the answers to these questions relate to what I am trying to prove?


Now, spend some time on this. You are giving up way too easily. Like I said, if you want to be successful at math, whether you are doing research, working in some applied area or teaching, you are going to have to figure stuff out for yourself. We have given you ample "hints" (we have, in fact, done much more than that), if you refuse to think about it, there really isn't a lot more that we can do.

It's an extra credit question it's obviously not as easy you say than the 5 hours i spent on the rest of the test.

 

[berkeman]

Unfortunately, Isaak is no longer with us. Thank you all for trying so hard to help him. Thread closed.