Nicole Steigerwald

CS 273 HW1

a. The (g(x)) = f(x) notation means that a function f(x) exists and is asymptotically lower bound by the function g(x) after a point defined by n0. In the case where a function f(x) is (1) then the function f(x) is greater than or equal to one at all points after a designated point n0.

b. If a function f(x) is O(x) then f(x) is O(x2). Because I know that x2 grows faster than x this statement seems like common sense. If a function is upper bounded by the linear function x than it obviously is bounded by x2 which grows more rapidly than x. This can also be proven by using the relational properties found in section 3.1 of CLRS (pg. 49). The transitivity property for O is:

f(n) = O(g(n)) and g(n) = O(h(n)) imply f(n) = O(h(n))

Theorem 1 in Rosen (pg 84) proves that x = O(x2) so I can substitute g(n) = x and

h(n) = x2. Therefore,

f(n) = O(x) and x = O(x2) imply f(n) = O(x2).

c. log99 n  lg n  n  ( )  nlg n n!

Proof:

2. In order to count the number of solutions to the equation

x1 + x2 + x3 + x4 = 18

which satisfy 1  x1  5

-2  x2  4

0  x3  5

3  x2  9

I used the principles of Inclusion/Exclusion. Each bound is defined as a property of the number of solutions. I began by counting the number of solutions (N) available given the lower bounds or the following properties.

P1 = the solution has the property 1  x1

P2 = the solution has the property -2  x2

P3 = the solution has the property 0  x3

P4 = the solution has the property 3  x2

N = P1 + P2 + P3 + P4 – (P1  P2 ) - (P1  P3 ) -(P1  P4 ) -(P2  P3 ) - (P2  P4 ) - (P3  P4 )

+ (P1  P2  P3 ) + (P1  P2  P4 ) + (P2  P3  P4 ) + (P1  P3  P4 )

- (P1  P2  P3  P4 )

To determine the number of solutions that have a given property or set of properties I added the bound(s) given by the property or properties together and subtracted the sum from the solution 18. This gives us the number that will be chosen as well as part of the total group we are choosing from.

P1 = C(4 + 17 – 1), 17) = 1140

P2 = C(4 + 20 – 1), 20) = 1771

P3 = C(4 + 18 – 1), 18) = 1330

P4 = C(4 + 15 – 1), 15) = 816

(P1  P2 ) = C(4 + 19 – 1), 19) = 1540

(P1  P3 ) = C(4 + 17 – 1), 17) = 1140

(P1  P4 ) = C(4 + 14 – 1), 14) = 680

(P2  P3 ) = C(4 + 20 – 1), 20) = 1771

(P2  P4 ) = C(4 + 17 – 1), 17) = 1140

(P3  P4 ) = C(4 + 15 – 1), 15) = 816

(P1  P2  P3 ) = C(4 + 19 – 1), 19) = 1540

(P1  P2  P4 ) = C(4 + 16 – 1), 16) = 969

(P2  P3  P4 ) = C(4 + 17 – 1), 17) = 1140

(P1  P3  P4 ) = C(4 + 14 – 1), 14) = 680

(P1  P2  P3  P4 ) = C(4 + 16 – 1), 16) = 969

This gives me N = 1330. There are 1330 possible solutions using only the lower bounds. I incorporated the upper bounds and repeated the process preformed above with the addition of 1 to each of the bounds to acquire the number of solutions (M) that are out of bounds.

P5 = the solution has the property x1  5

P6 = the solution has the property x2  4

P7 = the solution has the property x3  5

P8 = the solution has the property x2  9

M = P5 + P6 + P7 + P8 – (P5  P6 ) - (P5  P7 ) -(P5  P8 ) -(P6  P7 ) - (P6  P8 ) –

(P7  P8 ) + (P5  P6  P7 ) + (P5  P6  P8 ) + (P6  P7  P8 ) + (P5  P7  P8 )

- (P5  P6  P7  P8 )

P5 = C(4 + 12 – 1), 12) = 455

P6 = C(4 + 13 – 1), 13) = 560

P7 = C(4 + 12 – 1), 12) = 455

P8 = C(4 + 8 – 1), 8) = 165

(P5  P6 ) = C(4 + 7 – 1), 7) = 120

(P5  P7 ) = C(4 + 6 – 1), 6) = 84

(P5  P8 ) = C(4 + 2 – 1), 2) = 10

(P6  P7 ) = C(4 + 7 – 1), 7) = 120

(P6  P8 ) = C(4 + 3 – 1), 3) = 20

(P7  P8 ) = C(4 + 2 – 1), 2) = 10

(P5  P6  P7 ) = C(4 + 1 – 1), 19) = 5

(P5  P6  P8 ) = Solutions with these properties exceed 18 = 0

(P6  P7  P8 ) = Solutions with these properties exceed 18 = 0

(P5  P7  P8 ) = Solutions with these properties exceed 18 = 0

(P5  P2  P7  P8 ) = Solutions with these properties exceed 18 = 0

M = 1276

By eliminating the possible solutions that are out of bounds in the upper direction (M) from those found inside the lower bounds (N) the result is 1330 – 1276 or 54 possibilities for the proposed equation and constraints.

In order to find the coefficient of x14 in the binomial expression (2x +3)19 without using algebraic expansion I used the binomial theorem. The binomial theorem is

(x + y)n = ( ) xn-j yj

Assuming that n is a positive integer we can substitute x = 2x, y = 3, n = 19,

and j = 14. j= 14 because the term we are looking for is raised to the 14th power.

Plugging into the Binomial theorem gives:

( ) 2x14 * 35 = 46294695936

4. ( )( ) = ( )( )

In order to do a combinatorial proof of the above identity I will show that there are two methods that produce the same result and both of these methods are identified in the equation above .

For both methods assume:

n total people

m people in the committee

k chair people

Using either method we will result in a committee of m people with some of those m people acting as chair people (k). This group was always chosen from the larger group n.

a.k * k! = (n + 1)! – 1

Base Case:

For n = 1

1 * 1! = (1 + 1)! -1

1 = 2! -1

1 = 1

Inductive Hypothesis:

Assume

k * k! = (n + 1)! – 1

Inductive Step:

k * k! = (n + 2)! – 1

1*1! + 2*2! +…+ n*n! + (n+1) * (n+1)!

By Inductive Hypothesis

1*1! + 2*2! +…+ n*n! = k * k! = (n + 1)! – 1

so on the left side of the equation we have we have

(n + 1)! – 1 (n+1) * (n+1)!

= (n +1)! -1 +(n+1) * (n+1)!

= (n +1 + 1) (n+1)! -1

= (n + 2) (n + 1)! -1

= (n + 2)! -1

b. Assume:

I have the greatest paying job ever.

I get a bonus every year based on the number of years I work.

My salary is the product of all the salaries from the previous years I have worked.

To calculate my gross income from employment I can use one of two methods.

Both of the above methods yield the same result giving me two correct ways to count my money.

NOTE: The second part of the answer was found on However, before this solution was pointed out to me I thought I had something that was close to correct (the first part of the solution). I was hoping that if you had time you could review the first part and tell me how far I’m actually off. I can compare the two on my own I was just wondering how much credit I would have received if I went with my first answer. If time is not on your side please skip to section 2 for my answer.

(Part one) –read only if time allows

(x + y)n = ( ) xn-j yj

Base Case:

For n = 1

(x + y)1 = ( ) x1-j yj

= ( ) x1 y 0 + ( ) x0 y1

= x + y

x + y = x + y

Inductive Hypothesis:

Assume (x + y)n =  ( ) xn-j yj

Inductive Step:

(x + y)n+1 = ( ) xn-j yj

= ( ) xn-j yj+ ( ) xn+1-(n+1) yn+1 + ( )xn+1 y0

(adding 1 would result in two new terms one where x is raised to the n+1 and one where y is raised to the n+1 power)

= ( ) xn-j yj

= (x + y)n+1 (By inductive hypothesis)

(Part 2) Please Read and Grade

Base Case:

For n = 1

(x + y)1 = ( ) x1-j yj

= ( ) x1 y 0 + ( ) x0 y1

= x + y

x + y = x + y

Inductive Hypothesis:

Assume (x + y)n =  ( ) xn-j yj

Inductive Step:

(x + y)n +1 = x(x + y) n + y(x + y) n

= x ( ) xn-j yj + y ( ) xn-k yk (By inductive Hypothesis)

= ( ) xn-j+1 yj + ( ) xn-k+1 yk (Include new x and y insummation)

= xn+1+( ) xn-j+1 yj + ( ) xn-k+1 yk (remove the j = 0 term / pull out highest x term)

=xn+1 +( ) xn-j+1 yj + ( ) xn-j+1 yj (let j = k-1)

= xn+1 + ( ) xn-j+1 yj + yn+1 + ( ) xn-j+1 yj (pull out highest y term)

= xn+1 + yn+1 + [( ) + ( )] xn-j+1 yj (combine sums)

= xn+1 + yn+1 + ( ) xn-j+1 yj (by Pascal’s rule)

= ( ) xn-j+1 yj

If everyone got along and no one cared where they sat at Erin’s wedding it would be a perfect world and there would be 24! ways to arrange all of the guests. Because we are dealing with a circle 25! would over-count because there is no beginning or end of the circle. So Erin has 15511210043330985984000000 or 1.551 x 1025 ways to arrange the table.

b. Sitting Erin and Jeff next to one another results in treating them like one person and permutating the rest of the guests. We must also consider that of the 25 spots the Jeff/Erin pair begins with either could sit first. This means that the Jeff/Erin pair could be in one of 50 positions based only on their permutations. The rest of the guests sit in any of the remaining 23 seats giving us 22! ways to permute them. So in this situation there are 25 * 2 * 22! or 56200036388880384000000 or 5.62 x 1022 ways to arrange the table.

c. Keeping Erin and Jeff together and Jeff away from his psycho sister we seat Erin and Jeff in one of their 50 possible settings and permutated the rest of the guests. Next we subtract out all of the possible situations where psycho sis is sitting next to Jeff. (23 * 21!) The result is 50 * 22! – (23 *21!) or 55024944718931066880000 or 5.50 x 1022

d. To ensure that Erin sits next to one of her siblings we now treat the Jeff/Erin pair as a Jeff/Erin/Sister trio. Since Erin must always be in the middle we still have 50 places the trio can sit, but because the sister may be any of 3 people we must multiply by 3. Next we seat the other guests 21! ways and again subtract out all of the times psycho sis ends up next to Jeff. This results in 150 * 21! – (22 * 20!) or 7610117481576529920000 or

7.61 x 1021.

********************COLLABORATORS NOTICE********************

This homework brought to you through the collaborative efforts of Pat Bergschneider (his web capabilities and Math 213 notes) , Yoko Fujimaru (her notes from her last school), and Mike Pham (his Math 213 and CS 273 notes, and his fabulous calculator)