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.