Problem 1: I have an idea of how to solve this problem. I just need to prove that no matter what step we take from (m, n), except when m = 0 and n = 0, m and n will never be equal to each other. I could look up an example …
This chapter is about infinite sets and some challenges in proving things about them. There has been a truly astonishing outcome of studying infinite sets. Their study led to the discovery of fundamental, logical limits on what computers can possibly do. For example, in a later section, they use reasoning …
Recursive data - define something in terms of simpler version of the same thing. Recursive data types play a central role in programming, and induction is really all about them. Recursive data types are specified by recursive definitions, which say how to construct new data elements from previous ones. Along with …
State machines are a simple, abstract model of step-by-step processes. One of the most important uses of induction in computer science involves proving one or more desirable properties continues to hold at every step in a process. A property that is preserved through a series of operations or steps is …
Problem 1: I was able to get the base cases, but couldn’t make the jump to the induction step. I ended up looking at the solution. Problem 2: This was a little complicated, I didn’t even know where to start. So I looked up solution as well. Problem …
Induction is a powerful method for showing a property is true for all non-negative integers. Induction plays a central role in discrete mathematics and computer science. In fact, its use is a defining characteristic of discrete—as opposed to continuous—mathematics. This chapter introduces two versions of induction, Ordinary and …
We start by going over Functions. Its definition, what domains, codomains and images are, examples, and function composition. I was surprised to see some of the creative ways we can define a function. For example let f(y) be the length of a left to right search of the bits …
For problem 1, I follow the description’s equivalence formula of set theory. But for part (a) when it asks to write a formula Members(p, a, b) of set theory that means p = {a, b} I am lost. This must be something from the text book that was not …
Informally, a set is a bunch of objects, which are called the elements of the set. The elements of a set can be just about anything: numbers, points in space, or even other sets. The conventional way to write down a set is to list the elements inside curly-braces. This …
I didn’t find the first proofs to be easy. It required creative mathematical thinking using algebraic rules, some of which I have forgotten. To not waste too much time, I gave it an honest attempt for 16-32 min, then after I was surely stuck, I looked up the solution …