Lecture 6: Basic arithmetic and geometric sums, closed forms
In this lesson, we learn about arithmetic and geometric sums, how to represent and compute them, and how to write closed forms. We start off by looking at a simple recurrence equation of how much money you have in the bank and then move on to solving more complex recurrence equations. We then analyze the binary search algorithm and derive a big theta log N algorithm, which is a very fast algorithm for searching through large amounts of data. Overall, this lesson provides a good foundation for understanding and solving various mathematical problems using recurrence equations.
Learn about arithmetic and geometric sums, how to represent and compute them, and how to write closed forms.
More information about this course:
http://www.aduni.org/courses/discrete
Licensed under Creative Commons Attribution ShareAlike 2.0:
http://creativecommons.org/licenses/by-sa/2.0/
- Lecture Notes - Lecture Notes from the course
- Problem Set 3 - A problem set with some problems from this lecture
- Problem Set 3 Solutions - Solutions to the Problem Set
- What are recurrence equations and what do they have to do with induction?
- What is recursion?
- How is interest in bank accounts like a recurrence equation?
- How do you solve to find the closed form for a recurrence equation in the case of a bank account making 10% interest each year?
- What is binary search, what is the algorithm, how do you analyze its complexity, and what does it have to do with induction?
- What is the Towers of Hanoi problem?
- What is the recursive solution to the Towers of Hanoi problem, and how can you analyze its time complexity?
- What is the pseudo-code for solving the Towers of Hanoi problem recursively?
- How much time would it take to solve the Towers of Hanoi problem with 64 rings?
- What is a geometric series and what are some tricks for finding their sums?
- How do you find the sum of a geometric series?
- What is the sum of 1 + 2 + 4 + 8 + ... + 2^(n-1)?
- How do you show that the sum of x = 1/2 + 1/4 + 1/8 + ... = 1?
- What is the sum of 1/10 + 1/100 + 1/1000 + ... ?
- What is the sum of 1/10 + 2/10^2 + 3/10^3 + ... ?
- How can you draw a triangular graph with three vertices to solve the Towers of Hanoi problem?
- What is the six or seven rings problem or puzzle?
-
Staff Review
The main focus of this lesson is the Towers of Hanoi problem, which is a famous recursively solved problem that is often used as a childrenâs toy. A really fascinating view of the problem, its solution, and complexity. Then, geometric series and some variations of them are examined and their sums are found using some useful tricks. Finally, Towers of Hanoi are discussed using a graph with nodes and edges and the six / seven rings problem is introduced.
