Solutions Homework Exercises Week 2 - Wiskundige Methoden / Mathematical Methods - FEB21010(X) - Studeersnel (2024)

Vak

Universiteit

Erasmus Universiteit Rotterdam

Geüpload door:

Aanbevolen voor jou

• 16Uitwerkingen Tentamen Wiskunde 2, 1 Maart 2013Wiskunde 2Oefenmateriaal100% (9)
• 1Cheatsheet zonder tentamenvragenWiskunde 2Samenvattingen100% (9)
• 16Tentamen februari 2015, Vragen en antwoordenWiskunde 2Oefenmateriaal100% (9)
• 4Tussentoets januari 2015, vragen en antwoordenWiskunde 2Oefenmateriaal100% (7)
• 5Tentamen 1 maart 2013Wiskunde 2Oefenmateriaal100% (7)

Reacties

Andere studenten bekeken ook

• Samenvatting Wiskunde 2: werkgroep(en), differentievergelijkingen
• Verplichte opgaven, antwoorden huiswerk week 7 Differentievergelijkingen
• College 1 Sommencollege W2
• College 3 - Rente en meetkundige reeksen en matrices
• College 2 - Geavanceerd integreren

Gerelateerde documenten

• Formuleblad Wiskunde 2, Formuleblad is toegestaan tijdens het tentamen en zal dan verstrekt worden.
• Cheatsheet
• Differentiatievergelijkingen
• Samenvatting - Overzicht van formules Wiskunde 2
• Cheatsheet zonder tentamenvragen
• Formuleblad voor tentamen Wiskunde 2

Wiskundige Methoden / Mathematical Methods - FEB21010(X)

Solutions to homework exercises Week 2

2 Without repetition:

(

4

2

)

= 6,

(

6

3

)

= 20,

(

8

4

)

= 70.

With repetition:

(

4 + 2 − 1

2

)

= 10,

(

6 + 3 − 1

3

)

= 56,

(

8 + 4 − 1

4

)

= 330.

2 We need to prove that |X| =

(

n i

) (

n − i r − i

) (

n − r s − i

)

,

where X = {(A, B) : A ⊆ Nn, |A| = r, B ⊆ Nn, |B| = s, |A ∩ B| = i}.

Step 1: The left-hand side is already written as the number of elements in a set. Hence, we canskip Step 1.

Step 2: Define the set Y as follows

Y = {(D, E, F ) : D ⊆ Nn, |D| = i, E ⊆ Nn \ D, |E| = r − i, F ⊆ (Nn \ D) \ E, |F | = s − i}.

Note that any element (D, E, F ) ∈ Y can be obtained by first selecting D ⊆ Nn, then E ⊆ Nn \D,and finally F ⊆ (Nn \ D) \ E. For D ⊆ Nn with |D| = i we choose i elements from a set with|Nn| = n elements. This can be done in

(

n i

)

ways. For E ⊆ Nn \ D with |E| = r − i we

choose r − i elements from a set with |Nn \ D| = n − i elements. This can be done in

(

n − i r − i

)

ways. Finally, for F ⊆ (Nn \ D) \ E with |F | = s − i we choose s − i elements from a set with|(Nn \ D) \ E| = n − i − (r − i) = n − r elements. This can be done in

(

n − r s − i

)

ways. It followsthat|Y | =

(

n i

) (

n − i r − i

) (

n − r s − i

)

.

Step 3: Define now the function

f : X → Y with f ((A, B)) = (A ∩ B, A \ B, B \ A),and its inversef − 1 : Y → X with f − 1 ((D, E, F )) = (D ∪ E, D ∪ F ).

In order to show that we defined the function f correctly, we need to check that f is a well-definedfunction. Let (A, B) ∈ X, then f ((A, B)) = (A ∩ B, A \ B, B \ A) and

(a) A ∩ B ⊆ Nn and |A ∩ B| = i by definition of X ✓;(b) A \ B and A ∩ B are disjoint and A, B ⊆ Nn, hence A \ B ⊆ N \ (A ∩ B) and |A \ B| = |A \ (A ∩ B)| = |A| − |A ∩ B| = r − i ✓;

(c) B \ A and A ∩ B, A \ B are disjoint and A, B ⊆ Nn, hence B \ A ⊆ (Nn \ (A ∩ B)) \ (A \ B) and |B \ A| = |B \ (A ∩ B)| = |B| − |A ∩ B| = s − i ✓.

In order to show that f − 1 is indeed the inverse function of f , one needs to verify that

f − 1 (f ((A, B))) = (A, B) for all (A, B) ∈ X andf (f − 1 ((D, E, F ))) = (D, E, F ) for all (D, E, F ) ∈ Y.

For this, let (A, B) ∈ X. Then,

f − 1 (f ((A, B))) = f − 1 ((A ∩ B, A \ B, B \ A)) = ((A ∩ B) ∪ (A \ B), (A ∩ B) ∪ (B \ A)) = (A, B)

Similarly, let (D, E, F ) ∈ Y. Then,

f (f − 1 ((D, E, F ))) = f ((D ∪ E, D ∪ F )) = ((D ∪ E) ∩ (D ∪ F ), (D ∪ E) \ (D ∪ F ), (D ∪ F ) \ (D ∪ E)) = (D, E, F ) (because D, E and F are pairwise disjoint)

Hence, f − 1 is indeed the inverse function of f. Therefore, by the one-to-one rule, it holds that|X| = |Y | and thus also |X| =

(

n i

) (

n − i r − i

) (

n − r s − i

)

.

2 (a) We need to prove that ( n k

)

(n − k) =

(

nk + 1

)

(k + 1).

Step 1: Define the set X as follows

X = {(A, x) : A ⊆ Nn, |A| = k, x ∈ Nn \ A}.

Note that any element (A, x) ∈ X can be obtained by first selecting A ⊆ Nn, then x ∈ Nn\A.For A ⊆ Nn with |A| = k we choose k elements from a set with |Nn| = n elements. This canbe done in

(

n k

)

ways. For x ∈ Nn \A we choose an element from a set with |Nn \A| = n−kelements. This can be done in n − k ways. It follows that

|X| =

(

n k

)

(n − k).

Step 2: Define the set Y as follows

Y = {(B, y) : B ⊆ Nn, |B| = k + 1, y ∈ B}.

Note that any element (B, y) ∈ Y can be obtained by first selecting B ⊆ Nn, then y ∈ B.For B ⊆ Nn with |B| = k + 1 we choose k + 1 elements from a set with |Nn| = n elements.This can be done in

(

nk + 1

)

ways. For y ∈ B we choose an element from a set with|B| = k + 1 elements. This can be done in k + 1 ways. It follows that

|Y | =

(

nk + 1

)

(k + 1).

elements. This can be done in

(

n r

)

ways. For D ⊆ C with |D| = r − i we choose r − i elements

from a set with |C| = r elements. This can be done in

(

rr − i

)

ways. Finally, for E ⊆ Nn \ C

with |E| = s − i we choose s − i elements from a set with |Nn \ C| = n − r elements. This can

be done in

(

n − r s − i

)

ways. It follows that

|X| =

(

n r

) (

rr − i

) (

n − r s − i

)

.

Step 2: Define the set Y as follows

Y = {(F, G, H) : F ⊆ Nn; |F | = r + s − 2 i; G ⊆ Nn \ F ; |G| = i; H ⊆ F ; |H| = r − i}.

Note that any element (F, G, H) ∈ Y can be obtained by first selecting F ⊆ Nn, then G ⊆ Nn \Fand then H ⊆ F. For F ⊆ Nn with |F | = r + s − 2 i we choose r + s − 2 i elements from a set

with |Nn| = n elements. This can be done in

(

nr + s − 2 i

)

ways. For G ⊆ Nn \ F with |G| = i

we choose i elements from a set with |Nn \ F | = n − (r + s − 2 i) = n − r − s + 2i elements. This

can be done in

(

n − r − s + 2i i

)

ways. Finally, for H ⊆ F with |H| = r − i we choose r − i

elements from a set with |F | = r + s − 2 i elements. This can be done in

(

r + s − 2 i r − i

)

ways.

It follows that

|Y | =

(

nr + s − 2 i

) (

n − r − s + 2i i

) (

r + s − 2 i r − i

)

.

Step 3: Define now the function

f : X → Y with f ((C, D, E)) = (D ∪ E, C \ D, D),

and its inverse f − 1 : Y → X with f − 1 ((F, G, H)) = (G ∪ H, H, F \ H).

In order to show that we defined the function f correctly, we need to check that f is a well-definedfunction. Let (C, D, E) ∈ X, then f ((C, D, E)) = (D ∪ E, C \ D, D) and

(a) D ∪ E ⊆ Nn and |D ∪ E| = |D| + |E| = r − i + s − i = rs − 2 i by the sum rule because D and E are disjoint ✓;(b) C \ D ⊆ Nn \ (D ∪ E) because E and C are disjoint, and |C \ D| = |C| − |D| = r − (r − i) = i because D ⊆ C ✓;(c) D ⊆ D ∪ E and trivially |D| = r − i ✓.

In order to show that f − 1 is indeed the inverse function of f , one needs to verify that

f − 1 (f ((C, D, E))) = (C, D, E) for all (C, D, E) ∈ X andf (f − 1 ((F, G, H))) = (F, G, H) for all (F, G, H) ∈ Y.

For this, let (C, D, E) ∈ X. Then,

f − 1 (f ((C, D, E))) = f − 1 ((D ∪ E, C \ D, D)) = ((C \ D) ∪ D, D, (D ∪ E) \ D) = (C, D, (D ∪ E) \ D) (because D ⊆ C) = (C, D, E) (because D and E are disjoint)

Similarly, let (C, D, E) ∈ Y. Then,

f (f − 1 ((F, G, H))) = f ((G ∪ H, H, F \ H)) = (H ∪ (F \ H), (G ∪ H) \ H, H) = (F, (G ∪ H) \ H, H) (because H ⊆ F ) = (F, G, H) (because G and H are disjoint)

Hence, f − 1 is indeed the inverse function of f. Therefore, by the one-to-one rule, it holds that|X| = |Y | and thus also that ( n r

) (

rr − i

) (

n − r s − i

)

=

(

nr + s − 2 i

) (

n − r − s + 2i i

) (

r + s − 2 i r − i

)

.

2 We need to prove that

∑ n

i=

(

n r

) (

r i

) (

n − r s − i

)

=

(

n r

) (

n s

)

.

Step 1: Define for i ∈ N with 0 ≤ i ≤ n, the sets

Xi = {(A, B, C) : A ⊆ Nn, |A| = r, B ⊆ A, |B| = i, C ⊆ Nn \ A, |C| = s − i}.

Note that any element (A, B, C) ∈ Xi can be obtained by first selecting A ⊆ Nn, then B ⊆ Aand then C ⊆ Nn \ A. For A ⊆ Nn with |A| = r we choose r elements from a set with |Nn| = nelements. This can be done in

(

n r

)

ways. For B ⊆ A with |B| = i we choose i elements from

a set with |A| = r elements. This can be done in

(

ri

)

ways. Finally, for C ⊆ Nn \ A with|C| = s − i we choose s − i elements from a set with |Nn \ A| = n − r elements. This can be donein

(

n − r s − i

)

ways. It follows that

|Xi| =

(

n r

) (

ri

) (

n − r s − i

)

.

We now prove that Xi ∩ Xj = ∅ if i ̸= j. Select a triple (A, B, C) ∈ Xi. It then holds that|B| = i. If j ̸= i, the equation |B| = j does not hold. This shows that (A, B, C) ∈/ Xj if j ̸= i.This shows that the sets Xi, for i ∈ N with 0 ≤ i ≤ n, are pairwise disjoint. We can thus applythe sum rule, and find

|X 0 ∪... ∪ Xn| = |X 0 | +... + |Xn| =

∑ n

i=

|Xi| =

∑ n

i=

(

n r

) (

r i

) (

n − r s − i

)

.

Step 2: Define the set Y as follows

Y = {(D, E) : D ⊆ Nn, |D| = r, E ⊆ Nn, |E| = s}.

Note that any element (D, E) ∈ Y can be obtained by first selecting D ⊆ Nn and then E ⊆ Nn.For D ⊆ Nn with |D| = r we choose r elements from a set with |Nn| = n elements. This can be

Step 1: Define for k ∈ N with m ≤ k ≤ n, the sets

Xk = {(A, B) : A ⊆ Nn, |A| = k, B ⊆ A, |B| = m}.

Note that any element (A, B) ∈ Xk can be obtained by first selecting A ⊆ Nn and then B ⊆ A.For A ⊆ Nn with |A| = k we choose k elements from a set with |Nn| = n elements. This can be

done in

(

nk

)

ways. For B ⊆ A with |B| = m we choose m elements from a set with |A| = k

elements. This can be done in

(

km

)

ways. It follows that

|Xk| =

(

nk

) (

km

)

=

(

km

) (

nk

)

.

We now prove that Xk ∩ Xl = ∅ if k ̸= l. Select a pair (A, B) ∈ Xk. It then holds that |A| = k.If l ̸= k, the equation |A| = l does not hold. This shows that (A, B) ∈/ Xl if l ̸= k. This showsthat the sets Xk, for k ∈ N with m ≤ k ≤ n, are pairwise disjoint. We can thus apply the sumrule, and find

|Xm ∪... ∪ Xn| = |Xm| +... + |Xn| =

∑ n

k=m

|Xk| =

∑ n

k=m

(

km

) (

nk

)

.

Step 2: Define the set Y as follows

Y = {(C, D) : C ⊆ Nn, |C| = m, D ⊆ Nn \ C}.

Note that any element (C, D) ∈ Y can be obtained by first selecting C ⊆ Nn and then D ⊆ Nn\C.For C ⊆ Nn with |C| = m we choose m elements from a set with |Nn| = n elements. This can

be done in

(

nm

)

ways. For D ⊆ Nn \ C we choose from a set with |Nn \ C| = n − m elements.

This can be done in 2n−m ways. It follows that

|Y | =

(

nm

)

2 n−m = 2n−m

(

nm

)

.

Step 3: Define now the function

f : Xm ∪... ∪ Xn → Y with f ((A, B)) = (B, A \ B),

and its inverse

f − 1 : Y → Xm ∪... ∪ Xn with f − 1 ((C, D)) = (C ∪ D, C).

In order to show that we defined the function f correctly, we need to check that f is a well-definedfunction. Let (A, B) ∈ Xk, then f ((A, B)) = (B, A \ B) and

(a) B ⊆ Nn and |B| = m trivially; ✓(b) A \ B ⊆ Nn \ B. ✓

In order to show that f − 1 is indeed the inverse function of f , one needs to verify that

f − 1 (f ((A, B))) = (A, B) for all (A, B) ∈ Xk with k ∈ N, m ≤ k ≤ n, andf (f − 1 ((C, D))) = (C, D) for all (C, D) ∈ Y.

For this, let (A, B) ∈ Xk with k ∈ N, m ≤ k ≤ n. Then,

f − 1 (f ((A, B))) = f − 1 ((B, A \ B)) = (B ∪ (A \ B), B) = (A, B) (because B ⊆ A)

Similarly, let (C, D) ∈ Y. Then,

f (f − 1 ((C, D))) = f ((C ∪ D, C)) = (C, (C ∪ D) \ C) = (C, D) (because C and D are disjoint)

Hence, f − 1 is indeed the inverse function of f. Therefore, by the one-to-one rule, it holds that|Xm ∪... ∪ Xn| = |Y | and thus also

∑ n

k=m

(

km

) (

n k

)

= 2n−m

(

nm

)

.

2 Note that x 1 + x 2 +... + xn ≥ 1 + 2 +... + n = 12 n(n + 1). Hence, if a < 12 n(n + 1), then there are no solutions. First, we show that the number of solutions that satisfy the equality

x 1 + x 2 +... + xn = a, (1)

where xi ∈ N with xi ≥ i for i ∈ { 1 , 2 ,... , n} is equal to the number of solutions that satisfy theequality y 1 + y 2 +... + yn = a − 12 n(n + 1), (2)where y 1 , y 2 ,... , yn ∈ { 0 , 1 , 2 , ...}. For this, define

X = {(x 1 , x 2 ,... , xn) : x 1 + x 2 +... + xn = a, x 1 ∈ { 1 , 2 , 3 , ...}, x 2 ∈ { 2 , 3 , 4 , ...},... , xn ∈ {n, n + 1, n + 2, ...}}

and

Y = {(y 1 , y 2 ,... , yn) : y 1 + y 2 +... + yn = a − 12 n(n + 1), y 1 , y 2 ,... , yn ∈ { 0 , 1 , 2 , ...}}.

Then, |X| is the number of solutions to (1) and |Y | is the number of solutions to (2). We haveto prove that |X| = |Y |. In order to do so, define the function

f : X → Y with f ((x 1 , x 2 ,... , xn)) = (x 1 − 1 , x 2 − 2 ,... , xn − n),

and its inverse

f − 1 : Y → X with f − 1 ((y 1 , y 2 ,... , yn)) = (y 1 + 1, y 2 + 2,... , yn + n).

Note that f is well-defined function. To see this, let (x 1 , x 2 ,... , xn) ∈ X. Then, f ((x 1 , x 2 ,... , xn)) =(x 1 − 1 , x 2 − 2 ,... , xn − n) and

(a) x 1 − 1 + x 2 − 2 +... + xn − n = x 1 + x 2 +... + xn − 12 n(n + 1) = a − 12 n(n + 1); ✓(b) since for all i = 1,... , n we have that xi ∈ {i, i + 1,.. .}, then xi − i ∈ { 0 , 1 ,.. .}. ✓

(c) x 2 ∈ { 2 , 3 , 4 ,.. .} ⇒ x 2 − 2 ∈ { 0 , 1 , 2 , 3 ,.. .}; ✓(d) x 3 , x 4 ∈ { 0 , 1 , 2 ,.. .}; ✓(e) x 1 + x 2 + x 3 + x 4 ∈ { 3 , 4 , 5 ,... , 98 , 99 } ⇒ 99 − x 1 − x 2 − x 3 − x 4 ∈ { 0 , 1 , 2 , 3 ,.. .}. ✓

Note that f − 1 is indeed the inverse function of f. To see this, let (x 1 , x 2 , x 3 , x 4 ) ∈ X. Then,

f − 1 (f ((x 1 , x 2 , x 3 , x 4 ))) = f − 1 ((x 1 − 1 , x 2 − 2 , x 3 , x 4 , 99 − x 1 − x 2 − x 3 − x 4 )) = ((x 1 − 1) + 1, (x 2 − 2) + 2, x 3 , x 4 ) = (x 1 , x 2 , x 3 , x 4 ).

Similarly, let (y 1 , y 2 , y 3 , y 4 , y 5 ) ∈ Y. Then,

f (f − 1 ((y 1 , y 2 , y 3 , y 4 , y 5 ))) = f ((y 1 + 1, y 2 + 2, y 3 , y 4 )) = ((y 1 + 1) − 1 , (y 2 + 2) − 2 , y 3 , y 4 , 99 − (y 1 + 1) − (y 2 + 2) − y 3 − y 4 ) = (y 1 , y 2 , y 3 , y 4 , 96 − y 1 − y 2 − y 3 − y 4 ) = (y 1 , y 2 , y 3 , y 4 , y 5 ) (because (y 1 , y 2 , y 3 , y 4 , y 5 ) ∈ Y , so y 1 + y 2 + y 3 + y 4 + y 5 = 96)

Therefore, by the one-to-one rule, it holds that |X| = |Y |.Next, we want a formula for the number of solutions to (4). Every solution is a 96-combinationwith repetition from 5. Hence, the number of solutions satisfies

|Y | =

(

5 + 96 − 1

96

)

=

(

100

96

)

.

Therefore, also |X| =

(

100

96

)

and thus equation (3) has

(

100

96

)

solutions.

2 The solution to this question will be published separately after the exercise lecture (Lecture 4).