#1: a) Let a, b, c be integers and x is congruent to y (mod m). Prove that ax^2+bx+c is congruent to ay^2+by+c (mod m).
b) Show that the result in part a may be false if a, b, c are not all integers, even if ax^2+bx+c and ay^2+by+c are both integers.
#2: Let p: X --> Y and q: Y -->Z be functions such that (q(p)): X-->Z is onto. Prove that q is onto and give an example to show that p need not be onto.
#3: Give an algebraic proof to show that nCr = (n-1) C (r-1) + (n-1)C r.
Hi! Can some please help me with these problems? They are a little bit confusing and I am stuck on them.
Sure! I can help you with these problems. Let's break down each problem step by step:
#1:
a) To prove that ax^2+bx+c is congruent to ay^2+by+c (mod m), we can start by substituting the given congruence x ≡ y (mod m) into the equation ax^2+bx+c.
So, ax^2+bx+c ≡ ay^2+by+c (mod m)
Substituting x ≡ y (mod m), we get:
a(x^2-y^2)+b(x-y) ≡ 0 (mod m)
Now, we can factor out the common term (x-y) from the left side:
(x-y)(a(x+y)+b) ≡ 0 (mod m)
Since x ≡ y (mod m), we know that (x-y) is divisible by m. Therefore, we can divide both sides of the congruence by (x-y), resulting in:
a(x+y)+b ≡ 0 (mod m)
Finally, rearranging the equation gives us:
ax+ay+b ≡ 0 (mod m)
Which is equivalent to ay+by+c ≡ 0 (mod m)
Therefore, we have proven that ax^2+bx+c is congruent to ay^2+by+c (mod m).
b) To show that the result in part a may be false if a, b, c are not all integers, we can consider the following example:
Let a = 0.5, b = 1, c = 1, m = 2.
Consider the congruence x ≡ 1 (mod 2).
For x = 1, we have:
ax^2+bx+c = 0.5*1^2 + 1*1 + 1 = 2
Similarly, for y = 3 (which is congruent to 1 (mod 2)), we have:
ay^2+by+c = 0.5*3^2 + 1*3 + 1 = 9.5
Since 2 ≡ 0 (mod 2) and 9.5 ≡ 1.5 (mod 2), we can see that ax^2+bx+c is not congruent to ay^2+by+c (mod m) in this case.
Therefore, the result in part a may be false if a, b, c are not all integers, even if ax^2+bx+c and ay^2+by+c are both integers.
#2:
To prove that q is onto given the composite function (q(p)): X-->Z is onto, we can use the definition of onto functions.
Let's assume that q is not onto. This means that there exists a z in Z for which there is no y in Y such that q(y) = z.
Now, consider the composite function (q(p)): X-->Z. Since (q(p)) is onto, for every z in Z, there exists an x in X such that (q(p))(x) = z.
Since q(p) = q(p(x)) = z, there must exist a y in Y such that p(x) = y. However, we assumed that q is not onto, so there cannot be a y in Y for which q(y) = z. This leads to a contradiction because we have found an x in X for which p(x) = y and q(y) = z.
Therefore, our assumption that q is not onto must be false, and we can conclude that q is onto.
To show that p need not be onto, we can provide an example:
Let p: R --> R, where p(x) = x^2, and let q: R --> R, where q(x) = x. The composite function (q(p)): R --> R is onto because for every real number z, we can find x = √z such that (q(p))(x) = q(p(x)) = q(p(√z)) = q(z) = z. However, the function p(x) = x^2 is not onto because there is no real number y for which p(y) = -1.
Therefore, we have proven that q is onto, but p need not be onto.
#3:
To give an algebraic proof for nCr = (n-1)C(r-1) + (n-1)Cr, we can use the definition of combination (nCr) and the Pascal's identity.
nCr = n! / (r!(n-r)!)
(n-1)Cr = (n-1)! / ((r-1)!((n-1)-(r-1))!) = (n-1)! / ((r-1)!(n-r)!)
(n-1)C(r-1) = (n-1)! / ((r-1)!((n-1)-(r-1))!) = (n-1)! / ((r-1)!(n-r+1)!)
Adding (n-1)Cr and (n-1)C(r-1):
= (n-1)! / ((r-1)!(n-r)!) + (n-1)! / ((r-1)!(n-r+1)!)
= (n-1)!((n-r+1) + (n-r)) / ((r-1)!(n-r)!(n-r+1))
= n(n-1)! / (r!(n-r)!)
= n! / (r!(n-r)!)
This expression is equal to nCr, and thus we have proven that nCr = (n-1)C(r-1) + (n-1)Cr algebraically.
I hope that helps! Let me know if you have any further questions or if there's anything else I can assist you with.