Homework 11

Due: Dec 5th, 2021

Please create a LaTeX document using the code that has been posted in previous homework assignments. (Please update it to say Homework 11, with the correct due date, and including your name.)

Problems

This homework has four problems.

  1. Prove: Suppose \(f : A \to B\) is surjective. Then in function compositions \(f\) can be cancelled on the right, in the following sense. For any set \(C\) and functions \(g_1,g_2 : B \to C\), if \(g_1 \circ f = g_2 \circ f\), then \(g_1 = g_2\) (we can “cancel” the \(f\)s on the right).

    After your proof, give an example showing that \(f\) can’t necessarily be cancelled on the left, meaning give functions where \(f \circ g_1 = f \circ g_2\) but \(g_1 \neq g_2\).

    Hint: You’re trying to show that for every \(b \in B\), \(g_1(b)=g_2(b)\). What you know is that for every \(a \in A\), \((g_1 \circ f)(a) = (g_2 \circ f)(a)\). How can we connect those?

  2. For practice/review of induction, prove these statements using induction. (You might be able to prove them with other methods, such as modular arithmetic, but please use induction.)

    1. Find and prove a formula for \(2+5+8+11+\dotsb+(3n-1)\).

      Your formula will involve \(n^2\) but nothing higher than that. For homework, give a clear statement, like: “Claim: \(2+5+8+\dotsb+(3n-1) =\) (a formula)”, and then prove it. You do not need to write the steps you took to find the formula.

    2. Prove: For all positive odd integers \(n\), \(5^n - n^2\) is divisible by \(4\).

      (Positive odd integers means \(n=1,3,5,\dotsc\). You can either write an induction that takes steps of size \(2\), or else set \(n=2k+1\), so \(k=0,1,2,\dotsc\), and use “normal” induction with \(k\).)

  3. Proposition 11.25.

    This problem is less complicated than it might at first appear. They give you a formula for \(a_k\); plug that into the recurrence relation, and check that both sides come out to the same value, once you do some algebraic simplifications (group like terms and pull out common factors).

    Optional mini-challenge: If we started with a degree \(3\) equation \(x^3-bx^2-cx-d=0\), what kind of recursive sequence could we define?

  4. Finally, redo one problem from a previous homework assignment (not the one you did in Homework 10). Your score will count for this homework, not the previous one. Along with your answer, write a short reflection essay (1-2 paragraphs) about what you learned.

Additional assignments, required

These items are assigned and required. You do not have to turn in anything. These items will not be graded.

  • Read Chapter 13 of the textbook. That’s the last class material we’ll cover this semester.

  • Review for the final exam. More information will be posted soon. For now, briefly:

    • The final exam format will be essentially the same as our midterm exam.

    • There will be at least one question that asks you to write an induction proof (roughly similar level to the ones on this homework).

    • There will be at least one question that asks you to write a proof about injective/surjective/bijective functions (simpler/easier than the one on this homework).

    • Our final exam scheduled time is Monday, December 13, 12-2pm.

  • Please complete the course evaluation. Your feedback is valuable and helps me improve my teaching. Also, you can get a (small) extra credit for completing the course evaluation.

Instructions

Use LaTeX to create a PDF. Upload your PDF to Gradescope. If you don’t have LaTeX on your computer, you can use Overleaf. Don’t submit the LaTeX source, just the PDF. Email your instructor (that’s me) if you have questions or need help.

Please include your name and the homework number within the document. Some additional formatting instructions are in the syllabus. To summarize:

  • Use a new page (\newpage) for each problem.
  • State which question you are answering and the actual question. Then, start your answer in a new paragraph.

You are encouraged to work together on the homework!

Additional assignments, optional

These are optional (not required).

  • Please try to visit the Mathematics Senior Showcase on Thursday, December 9, 3:30-5:00, if you are able. This is where graduating seniors will show their senior thesis projects. It will be a lot of fun, you will get an understanding of where you will go in your degree, and you will also learn about some new math topics that you might like to follow up on. Zoom link posted in Canvas.

  • Do you remember the homework questions a while ago about summations of Fibonacci numbers and their squares, \(f_1+f_2+\dotsb+f_n\) and \(f_1^2+f_2^2+\dotsb+f_n^2\)? Please take a look at https://mathoverflow.net/a/12024/88133 which shows pictorially how the summation of the squares can be illustrated with a really cool picture of a Fibonacci spiral made of squares.

  • I’m sorry, I wasn’t able to put together a simple, easy tutorial on drawing Venn diagrams with TikZ. It’s not an impossible task, I just didn’t find the time to plan out how to include it in an assignment for this class. If you’re curious, you can find some instructions by searching online.

  • If you have any questions about this class, future math classes, registering for spring, etc., please feel free to visit my student times on Thursday or email me.