= k4 + 4 k3 + 6k2 +4k + 1 - k -1 – k4 + k
= 4 k3 + 6k2 +4k
P(k+1) – P(k) is not always divisible by x for P(n)= nx – n when x =4. It is only divisible when 6k2 is divisible by 4.
If x = 5, Difference = (k+1)5- (k +1) - k5 + k
= k5 + 5 k4 + 10k3 +10k2 + 5k+ 1 - k -1 – k5 + k
= 5 k4+ 10k3+10k2+ 5k
= 5 (k4+ 2k3+2k2+ k)
P(k+1) – P(k) is divisible by x for P(n)= nx – n when x =5.
iv) Using appropriate technology, explore more cases, summarize your results and make a conjecture for when nx – n is divisible by x.
If you type in this code into Maple 11, an all-purpose math software program developed by the University of Waterloo, a code that finds out: for which values of x will the expression P(n) = nx – n be divisible by x, and the program subs in the numbers 1-100 for you, the out put will be this:
Therefore, numbers 1,2, 3, 5, 7, 11, 13, 17, 19, 23, …97 all have the desired divisibility property. This suggests that numbers which are prime numbers as well as 1 all have this property. So if x = prime number or 1, P(n) = nx – n will be divisible by that prime number.
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, kN. Determine when k is a multiple of x.
i) Explain how to obtain the entries in Pascal’s Triangle
The entries in Pascal’s Triangle are obtained by :
On the 0th row, write only the number 1. Then, to construct the elements of following rows, add the number directly above and to the left with the number directly above and to the right to find the new value. If either the number to the right or left is not present, substitute a zero in its place.
The first five row of Pascal’s Triangle.
ii) Using appropriate technology, generate the first 15 rows
Using Maple 11, if we type in the following code, it will generate the first 15 rows of Pascal’s Triangle.
iii) State the relationship between the expression P(k+1) – P(k) and Pascal’s Triangle.
The coefficients of P(k+1) – P(k) correspond to the entries in Pascal’s triangle, excluding the first and last entries (the ones).
For example, as shown in #1,
Difference = P(k+1) - P(k) = (k + 1) x - (k +1) - kx + k
If x = 2, Difference = (k + 1) 2 - (k +1) – k2 + k
= k2 + 2k +1- k -1- k2+ k
= 2k
If x = 3, Difference = (k+1) 3 - (k +1) - k3+ k
= k3 + 3 k2 + 3k +1 - k -1 - k3 + k
= 3 k2 +3 k
If x = 4, Difference =(k+1) 4- (k +1) - k4+ k
= k4 + 4 k3 + 6k2 +4k + 1 - k -1 – k4 + k
= 4 k3 + 6k2 +4k
If x = 5, Difference = (k+1)5- (k +1) - k5 + k
= k5 + 5 k4 + 10k3 +10k2 + 5k+ 1 - k -1 – k5 + k
= 5 k4+ 10k3+10k2+ 5k
iv) Reconsider your conjecture and revise if necessary.
My conjecture: If any row of Pascal’s triangle, excluding the first and last, begins with a prime number or a 1, then every term in that row is divisible by that prime number. For example, if you number every row in Pascal’s triangle starting from by numbering the first row that consists of only one entry (one) as the zeroth row , you will find that if the number of the row is prime, excluding the first row, then every entry in that row is divisible by this prime number, excluding the first and last entry.
v) Write an expression for the xth row of Pascal’s Triangle
xth row: , , ,…. , .
= 1, x, ,…. , 1.
k is the Pascal’s coefficient, and x is the row number.
vi) Determine when k is a multiple of x.
This question can be taken two ways.
If we take it to mean to ask when individually, as one coefficient, k is a
multiple of x: then we can generate a code to determine when k will be a
multiple of x:
However, if we type in this code into Maple 11, this code yields this:
Which at first baffled me because, why are all the numbers k from 0 -100
a multiple of x? Then, I realized that the code was for if some entries in
a row of Pascal’s triangle were a multiple of the row number,
not all entries.
For example,
Row # 8 of Pascal’s triangle is :
1, 8, 28, 56, 70, 56, 28, 8, 1
We notice that 56 is a multiple of eight, however, 70 and 28 aren’t. What this program did was put “Is div when x = 8” because some entries, not all, in a row were a multiple of 8. However, what this problem probably meant to ask was when are all entries (except the first and last entry) in a row of Pascal’s triangle a multiple of the row number.
Hence, we know that all entries (except the first and last) in a row of Pascal’s triangle are a multiple of the row number when the row number is a prime number. We know this has to be true because we know from question #1 that the coefficients of P(k+1) – P(k) correspond to the entries in Pascal’s triangle, excluding the first and last entries (the ones). We also wrote a Maple program in question #1 that showed that P(k+1) – P(k) is divisible by x for P(n) = nx – n when x is a prime number or 1. Hence, we have already
shown that all entries (except the first and last entry) in a row of Pascal’s triangle are a multiple of the row number when the row number is a prime number or 1.
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.
i) Make conclusions regarding the the last result in part 2.
Therefore, all entries (except the first and last entry) in a row of Pascal’s triangle are a multiple of the row number when the row number is a prime number or 1.
ii) Make conclusions regarding the form of proof of induction used in this assignment
The logic behind the form of proof by induction used in this assignment is that since proving by induction always doesn’t work directly or easily. For example, one isn’t able to prove easily by induction directly that if x = 3 P(n) = n3 – n is divisible by 3. But however, one is able to prove that if x =3 , P(k+1) – P(k) is always divisible by 3.
The logic is:
We want to find out if P(n) = nx – n can be divided by x by induction:
I) Step 1: Prove it true for x =1.
P(n) = nx – n
P(1) = n1 – n = n – n = 0
0 is divisible by any number. Therefore, P(x =1) is divisible by 1.
II) Step 2: Assume it is true for n=k
P(k) is divisible by x.
III)Step 3: Prove it is true for n=k+1
It is not always easy or possible to prove this directly by induction. Therefore:
P(k+1) = [P(k+1) – P(k)] + P(k)
= The difference + P(k)
Since it is assumed in step two that P(k) is divisible by x, then if we prove that the difference [P(k+1) – P(k)] is divisible by x, then the whole thing is divisible by x.
iii)Refine your conjecture if necessary and prove it.
To prove that if any row of Pascal’s triangle, excluding the first and last entry, begins with a prime number, then every term in that row is divisible by that prime number we need to use the following concepts:
1.The ability to construct Pascal’s triangle and to relate the coefficients to the expansion of . (x + y)n
2. The formula =for the binomial coefficients is required.
3. A familiarity with prime numbers and the prime factorization of an integer.
4. The Fundamental Theorem of Arithmetic: Every integer greater than one can be written uniquely as a product of primes.
5. Euclid’s Lemma: If a, b, and c are natural numbers and a divides bc, with a and b having no prime factors in common (a and b are relatively prime), then a divides c.
The Proof itself:
We know that = . But is an integer, so the denominator r! divides the numerator. Let a = r! , b = p, and c = (p –1)(p – 2)…(p – r+1) in our statement of Euclid’s lemma. Since r < p, all of the prime factors of r! are less than p. Thus p and r! are relatively prime and Euclid’s lemma tells us that = q must be an integer. Hence = pq and therefore, p divides .
4. State the converse of your conjecture. Describe how you would prove whether or not the converse holds.
So to take the converse means that I have to go backwards. I have proved that if a row (except the first and last entry) of Pascal’s triangle starts with a prime number or one, every element in that row will be divisible by that number. And now I have to prove that if every element in a row of Pascal’s triangle (except the first and last entry) is divisible by a number, it is a prime number or one.
First, I would test each row and find the greatest common multiple for every entry excluding the first and the last, if there is one.
Second, I would list the greatest common multiples and note if it’s a prime number.
According to the Fundamental Theorem of Arithmetic, every integer greater than one can be written uniquely as a product of primes. Therefore, if every entry in a specific row of Pascal’s triangle has a greatest common multiple, then this greatest common multiple has to be a prime number. This is not necessarily true, you would have to prove it. The fundamental theorem of arithmetic doesn’t really apply here. The theorem only says that you can write a number in terms of prime factors. But the GCF of the row will not necessarily be a prime.
Take row 4: the entries are 1, 4, 6, 4, 1. The GCF is 2, which is a prime. But this row is not one of the rows that start with w prime number.
So there has to be other cases as well as this one.
This does not affect your conjectures. Because your conjectures doesn’t mention anything about the row being a prime number. It just says that the CGF is a prime.
Hence, if every element in a row of Pascal’s triangle (except the first and last entry) is divisible by a number, it is usually a prime number or one.
I would also create a program on Maple 11 to test and confirm this converse statement.
