## Lecture 5: Diagonalization, functions and sums review

Lecture 5: Diagonalization, functions and sums review
• Currently 4.0/5 Stars.
8593 views, 1 rating - 01:18:00
Part of video series ArsDigita Discrete Math Course
Taught by ArsDigita
Learn about diagonalization, functions, and a review of sums.
• What is a conundrome in Discrete Math?
• If there is a town in which everyone either shaves himself or goes to the barber, does the barber shave himself?
• Why is there no program that finds infinite loops in other programs?
• What is a function, and what does it mean for a function to have one-to-one correspondence?
• What is domain and range for a function?
• What does it mean for a function to be onto?
• Which is larger, x^(log x) or (log x)^x?
• What is the proof that 1^3 + 2^3 + 3^3 + ... + n^3 = (1 + 2 + 3 + ... + n)^2 using induction?
• How can you find and prove the sum of 1^2 + 2^2 + 3^2 + ... + n^2 without induction?
• How do you write and use sigma notation for sums?
• How do you find the sum of squares by finding the sum of consecutive odd integers and manipulating the sum?
• What is the sum of (n - i + 1)(2i - 1) from i = 1 to n?
This video starts out with an intriguing barber paradox, and uses this as an analogy to a computer program, and then outlines a proof by contradiction to say that such a program cannot exist. Then, functions are discussed in some detail. Next, some more about complexity with Big O and Big Theta are reviewed. Some really interesting and complex sums of series are calculated.
• Currently 4.0/5 Stars.
Reviewed by MathVids Staff on April 14, 2009.  