Discrete mathematics (PMI, composition, onto)

[Firestrider]

Homework Statement

a.)

F = {(1, a), (2, b), (3, a), (4, c)}
G = {(b, 1), (a, 2), (c, 3)}

i. Find F o G
ii. Find G o F

b.)

A function F: N x N --> N is represented 2(m + n) + 1 for F(m, n)

i. Is F one-to-one?
ii. Is F onto?

c.)

Prove by Mathematical Induction:

1^3 + 2^3 + 3^3 + ... + n^3 = [(n(n + 1))/ 2]^2 for all n element N.

Homework Equations

N/A

The Attempt at a Solution

a.)

i. {(1, (a, 2)), (2, (b, 1)), (3, (a, 2)), (4, (c, 3))}
ii. {((2, b), 1), ((1, a), 2), ((4, c), 3)}

b.)

I have no idea how to do this.

c.)

Well testing the base case of 1 since 1 is an element of N (natural numbers) the base case fails since 1^3 + 2^3 + 3^3 + ... 1^3 = 37 and [(1(1 + 1))/ 2]^2 = 1. 37 != 1. Therefore, the original statement is false.

 

[Mentallic]

I only understand the mathematical induction question, so I can help with that.

So we need to prove:
$$1^3+2^3+3^3+...+n^3=(\frac{n(n+1)}{2})^2$$

This means for the base case n=1, $$1^3=(\frac{1(1+1)}{2})^2$$

For n=2, $$1^3+2^3=(\frac{2(2+1)}{2})^2$$

For n=k, $$1^3+2^3+3^3+...+k^3=(\frac{k(k+1)}{2})^2$$

Do you see how this works now?

Now you must prove true for n=k+1

i.e. $$1^3+2^3+...+k^3+(k+1)^3=(\frac{(k+1)((k+1)+1)}{2})^2$$

But we have assumed that it is true for n=k, so this can be simplified:

$$(\frac{k(k+1)}{2})^2+(k+1)^3=(\frac{(k+1)((k+1)+1)}{2})^2$$

Did you see how this worked? All you need to do is prove the left side of the equation is equal to the right side.

 

[Tedjn]

a) F takes in a natural number and returns a letter. G takes in a letter and returns a number. Your solutions shows F compose G taking in a number and returning an ordered pair? How can you fix it?

b) Start with the definition of one-to-one and onto. What are they?

c) You are having trouble with the notation. Typically, the series is written out to 3^3 in order to make clear the pattern of summing up all the cubes of the integers from 1 to n. If n = 1, then you do not need to add to 3^3; you just stop at 1^3.

 

[Firestrider]

a) I might have this reversed but is it F o G = {(1, 2), (2, 1), (3, 2), (4, 3)} and G o F = {(2, 1), ((1, 3), 1), (4, 3)}

b) From my understanding one-to-one means that every element of set A is mapped to exactly one element is set B, and onto means that every element in set B has to be mapped.

c) Ok thanks for the help. I guess I didn't know how to do PMI when dealing with summations. I knew you must prove the base case is true, then formulate an induction hypothesis, and then prove the induction step. I thought you always had to use 1^3 + 2^3 + 3^3 on the LHS.

 

[HallsofIvy]

a) I might have this reversed but is it F o G = {(1, 2), (2, 1), (3, 2), (4, 3)} and G o F = {(2, 1), ((1, 3), 1), (4, 3)}

You should not have to guess about whether you have them reversed if you undstand what FoG and GoF mean- which is the main point of this problem. G goes from {a, b, c} to {1, 2, 3, 4} and F from {1, 2, 3, 4} to {a, b, c}. FoG goes from {a, b, c} to {1, 2, 3, 4} and then back to {a, b, c}: from {a, b, c} to {a, b, c}. The pairs for F o G should have only "a", "b", "c" in each pair. Conversely, G o F goes from {1, 2, 3, 4} to {a, b, c} and then back to {1, 2, 3, 4}: from {1, 2, 3, 4} to {1, 2, 3, 4}. The pairs in G o F should have only "1", "2", "3", "4" in each pair.

F o G(x) means F(G(x)). You are told that G(b)= 1 and that F(1)= a. Therefore FoG(b)= F(G(b))= F(1)= a. FoG(b)= 1 so (b, a) is in the "FoG" set. Follow that pattern to work out the rest.

b) From my understanding one-to-one means that every element of set A is mapped to exactly one element is set B, and onto means that every element in set B has to be mapped.

Yes, that is exactly right. Here, since F is from R², "one-to-one" means that two different pairs, (m,n) and (x,y), say, cannot be mapped onto the same thing. So a good way to approach this is to say "suppose F(m,n)= F(x,y)" and try to show that m= x and n= y. Here, F(m,n)= 2(m + n) + 1 and F(x,y)= 2(x+ y)+ 1. F(m,n)= F(x,y) means that 2(m+n)+ 1= 2(x+y)+ 1. Can you show that m= x and n= y from that or can you find different values of (m,n) and (x,y) that satisfy that? (Hint: what if m+n= x+ y? That is, what if m= 3, n= 2, x= 4, y= 1?)

"Onto" means that for any real number Y, there exist a pair (m,n) such that F(m,n)= 2(m+n)+ 1= Y. Can you solve that for (m, n)? Of course, if F is NOT one-to-one, there may be many such solutions.

(One kind of problem that comes up a lot in mathematics is 'existence and uniqueness'- showing that given problem (1) has a solution and (2) has only one solution. "Onto" says the solution to the problem F(m,n)= Y exists for all y and "one-to-one" says that solution is unique.)

c) Ok thanks for the help. I guess I didn't know how to do PMI when dealing with summations. I knew you must prove the base case is true, then formulate an induction hypothesis, and then prove the induction step. I thought you always had to use 1^3 + 2^3 + 3^3 on the LHS.

It is not proof by mathematical induction you have misunderstood but what is being asserted.

You are asked to prove that $1^3 + 2^3 + 3^3 + ... + n^3 = [(n(n + 1))/ 2]^2$ and seem to be under the impression that with n= 1 that is $1^3 + 2^3 + 3^3 + ... + 1^3 = [(1(1 + 1))/ 2]^2$ which is not at all true. The expression on the left means that you add cubes of consecutive integers up to n. If n= 1 you only have 1³ with no sum. If n= 2, 1³+ 2³, if n= 3, 1³+ 2³+ 3³, etc.