Answer to Question #137048 in Combinatorics | Number Theory for ANUSHIYA k

Question

(a) Prove the identity
1*1!+2*2!+3*3!+....+n*n!+(n+1)!-1
(b) discuss the combinatorial significance of this identity
(c)show that integer m can be expressed uniquely in the following form(factorial representation)
m=a1*1!+a2*2!+.......+ai*iI!+..
Where 0 less than or equal to ai less than or equal to i for i=1,2,3,4,.....

Answer 1

a) Proof: For n = 1, the statement reduces to 1(1!) = 2! − 1 and is obviously true. Assuming the statement is true for n = k: 1(1!) + 2(2!) + 3(3!) + · · · + k(k!) = (k + 1)! − 1 ,we will prove that the statement must be true for n = k + 1: 1(1!) + 2(2!) + 3(3!) + · · · + (k + 1)[(k + 1)!] = (k + 2)! − 1 . The left-hand side of 1(1!) + 2(2!) + 3(3!) + · · · + (k + 1)[(k + 1)!] = (k + 2)! − 1 can be written as 1(1!) + 2(2!) + 3(3!) + · · · + k(k!) + (k + 1)[(k + 1)!]. In view of 1(1!) + 2(2!) + 3(3!) + · · · + k(k!) = (k + 1)! − 1, this simplifies to: [1(1!) + 2(2!) + 3(3!) + · · · + k(k!)] + (k + 1)[(k + 1)!] = (k + 1)! − 1 + (k + 1)[(k + 1)!] = [1 + (k + 1)][(k + 1)!] − 1 = (k + 2)[(k + 1)!] − 1 = (k + 2)! − 1. Thus the left-hand side is equal to the right-hand side . This proves the inductive step. Therefore, by the principle of mathematical induction, the given statement is true for every positive integer n

b) whenever you have an induction problem like this that involves a sum, rewrite the sum using Σ

Σ-notation. It makes everything more concise and easier to manipulate:

c)The fundamental theorem of arithmetic:

Any positive integer can be divided in primes in essentially only one way. The phrase ‘essentially one way’ means that we do not consider the order of the factors important.

One is neither a prime nor composite number. One is not composite because it doesn’t have two distinct divisors. If one is prime, then number 6, for example, has two different representations as a product of prime numbers: 6 = 2 * 3 and 6 = 1 * 2 * 3. This would contradict the fundamental theorem of arithmetic.

Euclid’s theorem:

There is no largest prime number.

To prove this, let’s consider only n prime numbers: p1, p2, …, pn. But no prime pi divides the number

N = p1 * p2 * … * pn + 1,

so N cannot be composite. This contradicts the fact that the set of primes is finite.

Suppose that there are a finite number of primes, say a1, a2, . . . , an. Letm=a1*1!+a2*2!+.......+ai*iI!+... By the fundamental theorem of arithmetic, N is divisible by some prime a. This prime a must be among the ai , since by assumption these are all the primes, but N is seen not to be divisible by any of the ai , contradiction.