Proving K|n!+k for n≥2, k=2,3,4,...,n by Induction

[jonroberts74]

Homework Statement

prove by induction that K|n!+k for all integers n \ge 2 and k = 2,3,4,...,n
this one is different than other proofs I have had because I've only dealt with n changing but now n and k change.

k goes up to n, does this mean k and n have the same values?

for instance,

P(2)

2|2! + 2 \Rightarrow 2|4

so p(k)

is k|n!+k; n=k

k|k!+k

??

 

[Ray Vickson]

Homework Statement

prove by induction that K|n!+k for all integers n \ge 2 and k = 2,3,4,...,n



this one is different than other proofs I have had because I've only dealt with n changing but now n and k change.

k goes up to n, does this mean k and n have the same values?

for instance,

P(2)

2|2! + 2 \Rightarrow 2|4

so p(k)

is k|n!+k; n=k ??

You ask: "does this mean k and n have the same values?". No, that is not what it says and not what it means. Look at some small-n examples. If n = 3 it says that 2|3!+2 and 3|3!+3. So, k is not 3; it is any number in the set {2,3}. If n = 4 it says that all three of the statements 2|4!+2, 3|4!+3 and 4|4!+4 are true.

 

[jonroberts74]

ah okay

whatever n is, then k takes on each value in the set {2,...,n}

 

[HallsofIvy]

The fact that if k< n the n k divides n! makes this pretty close to trivial.

 

[jonroberts74]

2|n!+2
3|n!+3
4|n!+4
\downarrow
k|n!+k

where k takes on the values of 2,3,4...n and n is an integer greater than or equal to 2

and because for all k<n, k|n and when n=k, k|n

so my p(k) is

k|n!+k

and

p(k+1)

(k+1)|n!+(k+1)

 

[jonroberts74]

I have to make a correction. its not asking for induction. all the other problems on this problem set were induction but I confirmed with my prof this is not an induction proof question

 

[WWGD]

Can you see a common factor in the numerator?

 

[jonroberts74]

k is a factor of k, clearly and k is a also a factor of n! by the given information


2 \le k \le n and by definition of a factorial k had to be used somewhere along the product

\prod_{k=2}^{n} k

case 1

k = 2, n > or equal 2

\frac{2*...*n + 2}{2}

case 2

2 < k <n

\frac{2*...*k*...*n + k}{k}

case 3

n=k

\frac{2*...*k + k}{k}

 

[HallsofIvy]

Those case are not necessary. WWDG's point is that if k\le n then k is a factor of n!.

 

[jonroberts74]

I understand that but I am expected to show a proof. Seems a tad bit too easy to say if

k \le n then k is a factor of n!

 

[Ray Vickson]

I understand that but I am expected to show a proof. Seems a tad bit too easy to say if

k \le n then k is a factor of n!

But that is absolutely correct, so IS a proof! Sometimes proofs are easy---after you "see" them.