Investigating Divisibility
. Factorise the expression P(n) = nx - n for x ? {2, 3, 4, 5}. Determine if the expression is always divisible by the corresponding x. If divisible use mathematical induction to prove your results by showing whether P(k+1) - P(k) is always divisible by x. Using appropriate technology, explore more cases, summarize your results and make a conjecture for when nx - n is divisible by x.
.1 Factorise the expression P(n) = nx - n for x ? {2, 3, 4, 5}.
When n is real numbers;
x = 2 P(n) = n2 - n = n (n - 1)
x = 3 P(n) = n3 - n = n (n2 - 1) = n (n + 1) (n - 1)
x = 4 P(n) = n4 - n = n (n3 - 1) = n (n - 1) (n2 + n + 1)
x = 5 P(n) = n5 - n = n (n4 - 1) = n (n2 + 1) (n2 - 1)
= n (n2 + 1) (n - 1) (n + 1)
.2 Determine if the expression is always divisible by the corresponding x.
1.2.1 x = 2 P(n) = n2 - n = n (n - 1) divisible by 2?
When n = 1
n (n - 1) = 1 (1 - 1)
= 1 (0)
As 0÷2 = 0, P(n) is divisible by 2 when x = 2 and n = 1
Assume n = k is correct
k (k - 1) = k2 - k = 2M (where M is any natural number)
Then considering n = k + 1
(k + 1) (k) = k2 + k
= (k2 - k) +2k
= 2M + 2k
= 2(M + k)
Therefore, P(n) = n2 - n is divisible by 2 when x = 2 and n = any natural numbers.
1.2.2 x=3 P(n) = n (n + 1) (n - 1) divisible by 3?
When n = 1
n (n + 1) (n - 1) = 1 (2) (0)
= 0
As 0÷3 = 0, P(n) is divisible by 3 when x = 3 and n = 1
Assume n = k is correct
k (k + 1) (k - 1) = k (k2 - 1)
= k3 - k
= 3M (where M s any natural number)
Then considering n = k + 1
(k + 1) {(k + 1) + 1} {(k + 1) - 1} = (k + 1) (k + 2) (k)
As there is a multiplication of three consecutive integers, one of these three will always be a multiple of 3. Hence when x =3, P(n) = n (n + 1) (n - 1) is divisible by 3.
1.2.3 x = 4 P(n) = n (n - 1) (n2 + n + 1)
When n = 1
n (n - 1) (n2 + n + 1) = 1(0)(1 + 1 + 1)
= 0
As 0÷4 = 0, P(n) is divisible by 4 when n = 1.
Assume n = k is correct
k (k - 1) (k2 + k + 1) = 4M (where M is any natural number)
Considering n = k+1
(k + 1) {(k + 1) - 1} {(k + 1)2 + (k + 1) + 1} = (k + 1) (k) (k2 + 3k + 3)
As there is no 4 as a coefficient, which means it is not a multiple of four consecutive numbers, therefore when x = 4, P(n) = n (n - 1) (n2 + n + 1) is not divisible by 4.
1.2.4 x = 5 P(n) = n (n2 + 1) (n - 1) (n + 1)
When n = 1
n (n2 + 1) (n - 1) (n + 1) = 1 (2) (0) (2)
= 0
As 0÷5 is 0, P(n) is divisible by 5 when n = 1.
Assume n = k is correct
n (n2 + 1) (n - 1) (n + 1) = 5M (where M is any natural number)
Considering n = k + 1
(k + 1) {(k + 1)2 + 1} {(k + 1) - 1} {(k + 1) + 1} = (k + 1) (k2 + 2k + 2) (k) (k + 2)
= (k3 + 3k2 + 2k) (k2 + 2k + 2)
= k5 + 5k4 + 10k3 + 10k2 + 4k
As there is coefficient that is multiples of 5, when x = 5, P(n) = n (n2 + 1) (n - 1) (n + 1) is divisible by 5 when k is any natural number.
.3 If divisible use mathematical induction to prove your results by showing whether P(k+1) - P(k) is always divisible by x.
As P(n) = nx - n P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
1.3.1 x = 2
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)2 - (k + 1) - k2 + k
= k2 + 2k + 1 - k - 1 - k2 + k
= 2k
Therefore, as P(n) = nx - n and x = 2, P(k+1) - P(k) is divisible by x.
1.3.2 x = 3
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)3 - (k + 1) - k3 + k
= k3 + 3k2 + 3k + 1 - k - 1 - k3 + k
= 3k2 + 3k
= 3(k2 + k)
Therefore, as P(n) = nx - n and x = 3, P(k+1) - P(k) is divisible by x.
1.3.3 x = 4
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)4 - (k + 1) - k4 + k
= k4 + 4k3 + 6k2 + 4k + 1 - k - 1 - k4 + k
= 4k3 + 6k2 + 4k
For P(n) = nx - n and x ...
This is a preview of the whole essay
= 3k2 + 3k
= 3(k2 + k)
Therefore, as P(n) = nx - n and x = 3, P(k+1) - P(k) is divisible by x.
1.3.3 x = 4
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)4 - (k + 1) - k4 + k
= k4 + 4k3 + 6k2 + 4k + 1 - k - 1 - k4 + k
= 4k3 + 6k2 + 4k
For P(n) = nx - n and x = 4, P(k+1) - P(k) is not always divisible by x. Trial and error was used to find for which value of k will allow (k + 1)x - (k + 1) - kx + k to be divisible by x when x = 4.
1.3.4 x = 5
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)5 - (k + 1) - k5 + k
= k5 + 5k4 + 10k3 + 10k2 + 5k + 1 - k - 1 - k5 + k
= 5k4 + 10k3 + 10k2 + 5k
= 5(k4 + 2k3 + 2k2 + k)
Therefore, as P(n) = nx - n and x = 5, P(k+1) - P(k) is divisible by x.
.4 Using appropriate technology, explore more cases.
Graphics Display Calculator was used to explore more cases, x ? {2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13and 14}. From 1.1 to 1.3, x ? {2, 3, 4 and 5} are shown.
x = 6;
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)6 - (k + 1) - k6 + k
= k6 + 6k5 + 15k4 + 20k3 + 15k2 + 6k + 1 - k - 1 - k6 + k
= 6k5 + 15k4 + 20k3 + 15k2 + 6k
Therefore, as P(n) = nx - n and x = 6, P(k+1) - P(k) is not divisible by x.
x = 7;
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)7 - (k + 1) - k7 + k
= k7 + 7k6 + 21k5 + 35k4 + 35k3 + 21k2 + 7k + 1 - k - 1 - k7 + k
= 7k6 + 21k5 + 35k4 + 35k3 + 21k2 + 7k
= 7(k6 + 3k5 + 5k4 + 5k3 + 3k2 + k)
Therefore, as P(n) = nx - n and x = 7, P(k+1) - P(k) is divisible by x.
x = 8;
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)8 - (k + 1) - k8 + k
= k8 + 8k7 + 28k6 + 56k5 + 70k4 + 56k3 + 28k2 + 8k + 1 - k - 1 - k8 + k
= 8k7 + 28k6 + 56k5 + 70k4 + 56k3 + 28k2 + 8k
Therefore, as P(n) = nx - n and x = 8, P(k+1) - P(k) is not divisible by x.
x = 9;
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)9 - (k + 1) - k9 + k
= k9 + 9k8 + 36k7 + 84k6 + 126k5 + 126k4 + 84k3 + 36k2 + 9k + 1 - k - 1 - k9 + k
= 9k8 + 36k7 + 84k6 + 126k5 + 126k4 + 84k3 + 36k2 + 9k
Therefore, as P(n) = nx - n and x = 9, P(k+1) - P(k) is not divisible by x.
x = 10;
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)10 - (k + 1) - k10 + k
= k10 + 10k9 + 45k8 + 120k7 + 210k6 + 252k5 + 210k4 + 120k3 + 45k2 + 10k + 1 - k - 1 - k10 + k
= 10k9 + 45k8 + 120k7 + 210k6 + 252k5 + 210k4 + 120k3 + 45k2 + 10k
Therefore, as P(n) = nx - n and x = 10, P(k+1) - P(k) is not divisible by x.
x = 11;
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)11 - (k + 1) - k11 + k
= k11 + 11k10 + 55k9 + 165k8 + 330k7 + 462k6 + 462k5 + 330k4 + 165k3 + 55k2 + 11k + 1 - k - 1 - k11 + k
= 11k10 + 55k9 + 165k8 + 330k7 + 462k6 + 462k5 + 330k4 + 165k3 + 55k2 + 11k
= 11(k10 + 5k9 + 15k8 + 30k7 + 42k6 + 42k5 + 30k4 + 15k3 + 5k2 + k)
Therefore, as P(n) = nx - n and x = 11, P(k+1) - P(k) is divisible by x.
x = 12;
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)12 - (k + 1) - k12 + k
= k12 + 12k11 + 66k10 + 220k9 + 495k8 + 792k7 + 924k6 + 792k5 + 495k4 + 220k3 + 66k2 + 12k + 1 - k - 1 - k12 + k
= 12k11 + 66k10 + 220k9 + 495k8 + 792k7 + 924k6 + 792k5 + 495k4 + 220k3 + 66k2 + 12k
Therefore, as P(n) = nx - n and x = 12, P(k+1) - P(k) is not divisible by x.
x = 13;
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)13 - (k + 1) - k13 + k
= k13 + 13k12 + 78k11 + 286k10 + 715k9 + 1287k8 + 1716k7 + 1716k6 + 1287k5 + 715k4 + 286k3 + 78k2 + 13k + 1 - k - 1 - k13 + k
= 13k12 + 78k11 + 286k10 + 715k9 + 1287k8 + 1716k7 + 1716k6 + 1287k5 + 715k4 + 286k3 + 78k2 + 13k
= 13(k12 + 6k11 + 22k10 + 55k9 + 99k8 + 132k7 + 132k6 + 99k5 + 55k4 + 22k3 + 6k2 + k)
Therefore, as P(n) = nx - n and x = 13, P(k+1) - P(k) is divisible by x.
x = 14;
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)14 - (k + 1) - k14 + k
= k14 + 14k13 + 91k12 + 364k11 + 1001k10 + 2002k9 + 3003k8 + 3432k7 + 3003k6 + 2002k5 + 10014 + 364k3 + 91k2 + 14k + 1 - k - 1 - k14 + k
= 14k13 + 91k12 + 364k11 + 1001k10 + 2002k9 + 3003k8 + 3432k7 + 3003k6 + 2002k5 + 10014 + 364k3 + 91k2 + 14k
Therefore, as P(n) = nx - n and x = 14, P(k+1) - P(k) is not divisible by x.
.5 Summarize your results and make a conjecture for when nx - n is divisible by x.
As state above, it is proven that for P(n) = nx - n, when x is a prime number, then P(n) is divisible by x.
2. Explain how to obtain the entries in Pascal's Triangle, and using appropriate technology, generate the first 15 rows. State the relationship between the expression P(k+1) - P(k) and Pascal's Triangle. Reconsider your conjecture and revise if necessary.
Write an expression for the xth row of Pascal's triangle. You will have noticed that = k, k ? N. Determine when k is a multiple of x.
2.1 Explain how to obtain the entries in Pascal's Triangle.
Geometric arrangement of the binomial coefficient is known as Pascal's triangle. The number of rows starts with the row 0 to row x. To obtain number of terms in each row is found through the formula, n + 1, as n is represented as number of rows. To create the Pascal's triangle, start with the row 0, there is only one term and write 1. Then moving on to the row 1, using the formula above n+1, there are two terms. Each term represents addition of the two terms that are directly up-right and up-left. Same goes for row 2, row 3, row 4 and so on.
2.2 Use appropriate technology, generate the first 15 rows.
By using Microsoft Excel, Pascal's triangle is generated by using the excel formula.
For example, (O , 5) is addition of (P , 4) and (N , 4)
2.3 State the relationship between the expression P(k+1) - P(k) and Pascal's Triangle.
As shown in 1.3, As P(n) = nx - n P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
2.3.1 x = 2
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)2 - (k + 1) - k2 + k
= k2 + 2k + 1 - k - 1 - k2 + k
= 2k
2.3.2 x = 3
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)3 - (k + 1) - k3 + k
= k3 + 3k2 + 3k + 1 - k - 1 - k3 + k
= 3k2 + 3k
2.3.3 x = 4
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)4 - (k + 1) - k4 + k
= k4 + 4k3 + 6k2 + 4k + 1 - k - 1 - k4 + k
= 4k3 + 6k2 + 4k
2.3.4 x = 5
P(k+1) - P(k) = (k + 1)x - (k + 1) - kx + k
= (k + 1)5 - (k + 1) - k5 + k
= k5 + 5k4 + 10k3 + 10k2 + 5k + 1 - k - 1 - k5 + k
= 5k4 + 10k3 + 10k2 + 5k
The relationship between the Pascal's triangle and P(k+1) - P(k) is that the coefficient of P(k+1) - P(k) is the number inside the Pascal's triangle excluding the 1s on the side. (Note that the row number in Pascal's triangle is equal to x-1's P(k+1) - P(k))
2.4 Reconsider your conjecture and revise if necessary.
My conjecture is that inside Pascal's triangle, any row that contains a prime number or 1 in the second box (see picture below), then all the terms excluding the first and the last term in that row is a multiple of each designated prime number or 1.
For example;
1) Row 0 contains only one term, which is number 1. As 1 is a multiple of 1, my conjecture is true.
2) Row 1 contains two terms, which is 1 and 1. Same as row 0, as 1 is a multiple of 1, my conjecture is true.
3) Row 5 contains six terms; 1, 5, 10, 10, 5 and 1. Excluding first and last term, rest of them are multiple of designated prime number which is 5. Therefore, my conjecture is true.
2.5 Write an expression for the xth row of Pascal's triangle.
As 5th row consists of; 1, 4, 6, 4 and 1, which is
Therefore, for xth row of Pascal's triangle would be consisting;
2.6 You will have noticed that = k, k ? N. Determine when k is a multiple of x.
Considering k is the coefficient, and the x is the row number, as stated above in 2.4, any row that contains a prime number or 1 in the second box, then all the terms excluding the first and the last term in that row is a multiple of each designated prime number or 1. Then we know that when the second box contains a prime number, all the terms in that row is a multiple of x. Note that when r is equal to 1 or x, then = 1, hence this term is excluded. This could also be proven in question 1 as the coefficients of P(k + 1) - P(k) match up with the terms in Pascal's triangle, excluding the first and last term.
When the second box has a composite number, not all of the terms in that row are multiples of designated composite number. As stated from 1.5, when x is a composite number, P(n) could be divisible by x when n is prime number or a multiple of x, similarly in Pascal's triangle, when r is a prime number in and x is a composite number, then that term in row x is a multiple of designated composite number.
3. Make conclusions regarding the last result in part 2 and the form of proof by induction used in this assignment. Refine your conjecture if necessary, and prove it.
3.1 Make conclusions regarding the last result in part 2.
To summarise, in Pascals' triangle, when x is the prime number in and r is any number between 1 and x - 1, any term in that row is a multiple of designated prime number.
3.2 Make conclusions regarding the form of proof by induction used in this assignment.
In 1.2, it was asked to determine if the expression, P(n) = nx - n, is always divisible by the corresponding x. In order to prove this statement with induction, three steps had to be made.
1) First step was to let x = 1.
Then the expression changes into P(n) = n - n = 0.
Since 0 can be divided by any number, hence, P(n) is divisible by 1 when x = 1.
2) Second step was to let n = k and assume that statement is correct.
Since it is assumed to be correct, P(k) is divisible by x.
3) As second step is correct, third step was to let n = k + 1 and prove that it is true.
Therefore, the statement, P(k + 1) = {P(k + 1) - P(k)} + P(k), formed. By referring back to second step, that P(k) is assumed to be correct, then when P(k + 1) - P(k) is proved that it is correct, then the whole statement is proved correct that it is divisible by x.
3.3 Refine your conjecture if necessary, and prove it.
Following concepts are needed in order to prove my conjecture, where in any row of Pascal's triangle, excluding first term and last term, which starts with a prime number, then any term in that row is a multiple of designated prime number;
1) Using Pascal's triangle to gain (x + y)n form
2) Prime number and prime factorization of an integer
3) Euclid's Lemma
4)
To give more information on Euclid's Lemma, it is an important lemma considering on prime numbers and divisibility. It is basically stating that a prime number that can divide a product of two numbers must be able to divide one of two integers.
For example, 24 is a product of 8 and 3, and prime number that can divide 8 is 2 and 3. Hence prime number 2 can divide 8 and prime number 3 can divide 3.
At this stage, a generalised statement could be made where if n can divide a x b, and n and a are respectively prime, then n can divide b.
To prove my conjecture;
It is known that . However, is an integer, therefore the denominator, which is k!, divides the numerator. By putting n = k!, a = n and b = (n - 1)(n - 2)(n - 3)(n - k + 1), the generalised statement of Euclid's Lemma could be formed. Therefore, it could be said that n and a are respectively prime. Then, from Euclid's Lemma, it shows that = c, where c is an integer. Hence, it forms = c x n. Therefore, n divides when n is prime.
4. State the converse of your conjecture. Describe how you would prove whether or not the converse holds.
Converse means words so related that one reverses the relation denoted by the other. Hence, stating the converse of my conjecture simply means to rewrite my conjecture backwards.
My original conjecture was in Pascals' triangle, when x is a prime number in and r is any number between 1 and x - 1, any term in that row is a multiple of designated prime number x.
Converse of this would be, if every term in a row in Pascal's triangle, excluding first term and last term, are able to be divisible by a certain number, then that certain number is 1 or a prime number.
To investigate whether this converse of my conjecture holds, firstly I would examine each term of each row whether it has a common factors. Then, by listing out all the common factors, it then could be determined whether the common factors are 1 or a prime number or not. If all the common factors are 1 or prime number, then the converse holds. However, if the common factors are not 1 or prime number, the converse of my original conjecture is false.
For example, row 6 contains; 6, 15, 20, 15, 6 (excluding 1st and last term). The common factors of these terms would be 1. Hence, the converse holds.
Examine row 4 which contains; 4, 6, 4 (excluding 1st and last term). The common factors of these terms would be 1 and 2. Hence, as 2 is a prime number, the converse holds.
Another example would be row 9. Row 9 contains; 9, 36, 84, 126, 126, 84, 36, 9 (excluding 1st and last term). The common factors of these terms would be 1, 2 and 3. All of these three common factors are prime number, hence the conjecture holds.
By considering these examples, it could be stated that the converse of my original conjecture is proved that it holds.
