We Have Numbers Of Free Samples

1.)  Consider the following standard trigonometric equations:

cos(x + y) = cos(x) cos(y) − sin(x) sin(y)

sin(x + y) = sin(x) cos(y) + cos(x) sin(y)

Use these formulas and simple induction to prove that for all n ∈ N, n ≥ 1 and all x ∈ R,

(cos(x) + isin(x)) ⁿ = cos(nx) + isin(nx).

Recall that i is the “imaginary unit”, i.e., the square root of −1 (so i ² = −1).

Solution:

We need to prove using simple induction that for all n ∈ N, n ≥ 1 and all x ∈ R,

(cos(x) + isin(x))ⁿ = cos(nx) + isin(nx).

We are given that

cos(x + y) = cos(x) cos(y) − sin(x) sin(y)

sin(x + y) = sin(x) cos(y) + cos(x) sin(y)

First of all , the theorem is true for n = 1, because both sides of the equation are the same quantity if we put n=1. So now we will assume that the theorem has been shown true for n = k. We want to show that it is true for n = k + 1

We calculate:

[cos(x) + i sin(x)]^(k+1) =   [cos(x) + i sin(x)]^k * [cos(x) + i sin(x)]  (split up)

=  [cos(kx) + i sin(kx)] * [cos(x) + i sin(x)]                              (induction hypothesis)

=  cos(kx)cos(x) – sin(kx)sin(x) + i[sin(kx)cos(x) +  cos(kx)sin(x)]        (multiply out)

=  cos(kx + x) + i sin(kx + x)                                                    (use trig formulas)

=  cos((k+1)x) + i sin((k+1)x).                                                   (add the angles)

This proves the inductive step, so given Theorem has been shown to be true for all positive integers n.

2.)  Consider the following solitaire game, played with a collection of an identical coins.

• At any time during the game, the coins are divided into a number of groups. At the beginning, all the coins are in the same group.
• The game is played in rounds. During each round, you pick one of the existing groups (any one) that contains more than one coin and you split it into two smaller groups (in any way you like).
• Your gain in that round is the product of the sizes of the two new groups, in dollars!
• The game is over once every group contains exactly one coin.

For example, suppose you start with 13 coins. For your first round, you may decide to split the group into a group of 6 and a group of 7: this pays 6 × 7 = 42 dollars. In the next round, if you break the 7-coin group into a group of 2 and a group of 5, you will get 10 more dollars (for a total of 52 dollars so far). And so on.

Use induction to prove that for any natural number n ≥ 1, if you start the game with a single group of n coins, then regardless of how you play the game (i.e., no matter how you choose to split up the groups), you always win a total of exactly n(n − 1)/2 dollars.

Solution:

Let’s assume we have total k number of coins. We now split it into 2 group of size m and (k-m) . By the inductive hypothesis, these two groups will end up with a sum of products of m*(m-1)/2 and (k-m)*(k-m-1)/2 respectively, but we also obtained a product of  m(k−m) by this very split.

Hence, the eventual sum of products will be:

    m*(m-1)/2 + (k-m)*(k-m-1)/2 + m*(k-m)

= {m*(m-1) + (k-m)*(k-m-1) + 2m*(k-m)}/2

= {m² – m + k² – mk – k – mk + m² + m + 2mk – 2m²}/2

= (k²-k)/2

= k(k-1)/2

Hence proved

3.) Use the Principle of Well-Ordering to prove that for all-natural numbers n ≥ 1, there exists an odd natural number m and k ∈ N such that n = 2^k × m.

Solution:

Case 1: let n = 1

1 = 2⁰ x 1

Hence m will be 1 which is odd number.

Case 1: let us take n as odd number

Then we must have k = 0, since 2^k will always be a even number and multiplication by even number yields even number only while we have n as odd number.

            In this case      n = 2⁰ x m

                                    n = m

            Since n is odd, hence m will always be odd.

Case 2: n as even number.

            Then we can take n as 2 * a where a is some odd number. So

                                    2 x a = 2^k x m

                                    a = (2^k x m)/2

                                    a = 2^k-1  x m

                                    a = m               (since a is an odd number)

from the above solution, k can only be 1 (odd) and m will be odd too since a is odd.

4.) Consider a full trinary tree with more than one node. By the recursive definition it consists of a root with three children each of which is a full trinary tree.

Call them TA, TB, and TC. Then L = LA+LB +LC, and I = IA+IB +IC+1. By the IH, LA = 2IA + 1, LB = 2IB + 1, and LC = 2IC + 1. Summing these last three equations gives: LA + LB + LC = (2IA + 1) + (2IB + 1) + (2IC + 1) = 2(IA + IB2IC) + 3 By substitution L = 2(I − 1) + 3 = 2I + 1.

Solution:

full ternary tree                       L = 2I + 1

One node: L = 1 and I = 0. Then 2I + 1 = 2 · 0 + 1 = 1 = L.

Assume that for all trees with fewer than L leaves: L ′ = 2I ′ + 1

Let T be a tree with L leaves. Find an internal node for which all of its children are leaves. Remove the three children. The new tree has L − 2 leaves (having lost three but gained one) and I − 1 internal nodes (having lost one). By the IH, L − 2 = 2(I − 1) + 1, which implies L = 2I + 1.

[Download not found]

Download