Proof by Induction with a Mod

  • #1
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)
 

Answers and Replies

  • #2
SammyS
Staff Emeritus
Science Advisor
Homework Helper
Gold Member
11,391
1,044
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 )​
 
  • #3
... 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
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)
 
  • #6
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
35,237
7,057
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) [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
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) .
 
Last edited:
  • #9
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
 
  • #10
35,237
7,057
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) [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
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
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
35,237
7,057
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.
 
  • #15
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)?
 
  • #16
35,237
7,057
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 gonna 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.
 
  • #17
Well I don't know what you mean by "the definition of 0 mod n"
But I'll go your way I suppose.
 
  • #18
35,237
7,057
If [itex] x \equiv 0 (\text{mod n})[/itex], that means that x is an integer multiple of n.
 
  • #19
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
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
???
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?
 
  • #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.
 
Last edited:
  • #24
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.
 
Last edited:
  • #25
35,237
7,057
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 [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?
 

Related Threads on Proof by Induction with a Mod

  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
888
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
2
Views
780
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
9
Views
1K
Top