INSTRUCTIONS This homework should be done in groups of one to four students, without assistance from anyone besides the instructional staff and your group members. Homework must be submitted through Gradescope by a single representative of your group and received by 11:59pm on the due date. Students should consult their textbook, class notes, lecture slides, podcasts, group members, instructors, TAs. and tutors when they need help with homework. You may ask questions about the homework in office hours, but questions on Piazza should be private, visible only to instructors. This assignment will be graded for not only the correctness of your answers, but on your ability to present your ideas clearly and logically. You should explain or justify, present clearly how you arrived at your conclusions and justify the correctness of your answers with 111athematically sound reasoning {unless explicitly told not to). Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound. KEY CONCEPTS Binomial coefficient identities, stars and bars (Note: For this homework, you can leave your answers in terms of exponentials, factorials, binomial coefcients, etc.) (Note: for justifying counting arguments, a good rule of thumb is to explain how you came up with every term and factor of your answer. You can leave your answer in terms of exponentiols, foctorials and binomial coeicients rather than compute the exact numerical value.) 1. For n 2 (I consider the identity: 3" " w2"+ " *21+ " .22+...+ " '2""'+ n :2" _ u 1 2 n1 n {a} {5 points} Prove it using the binomial theorem (b) (10 points) Prove it combinatorially by counting the same set in two different ways. (Hint: you can count the set of n-length strings over the alphabet: {I}, 1, 2}.] 2. {10 points} For n 2 k, prove that: using a combinatorial argument. [Hint: count the number of ways to distribute in knights into k castles in two different ways,{ea:tra hint: base your counting on how many castles are empty