Discrete Mathematics - Midterm 1

Table of Contents

Exam Date
28th of October

1. Propositional Logic

1.1. Propositions

  • A proposition is a sentence which can be given a truth value of True or False.
  • Propositions can be related to each other using operators

1.1.1. Tautology

It is a proposition that can only be True.

\[ p \lor \neg q = \top \]

1.1.2. Contradiction

It is a proposition that can only be False.

\[ p \land \neg q = \bot \]

1.2. Operators

There are three main operators which can be used to express any logical expression. These consists of Not, Conjunction, Disjunction.

1.2.1. Not

It flips the truth value of a proposition.

\[ \neg p, \bar{A} \]

1.2.2. Conjunction

This operators returns a new truth value which is true if both of the propositions are true

\[ p \land q, AB \]

1.2.3. Disjunction

Like the conjunction, it operates on two propositions. It will return true as long as either of the propositions is true.

\[ p \lor q, A+B \]

1.2.4. Exclusive OR (XOR)

It is very similar to the Disjunction except that it must be exclusively one value that is true.

\[ \oplus = (p \lor q) \land \neg(p \land q) \]

1.2.5. Conditional Statements / Implication

A conditional statement consists of two parts, the premise and consequence. The truth value is only false when \(T \to F\).

\[ p \to q \equiv \neg p \lor q \]

  • If \(p\) is True, then \(q\) must also be True, we say that p is a sufficient condition for \(q\). \(T \to T\)
  • If \(p\) is False, \(q\) could still be True. \(F \to T\)
  • \(p\) cannot be true if \(q\) is not true. \(F \to F\)
  • \(p\) could still be false, even if \(q\) is true. \(F \to T\)

\[ ((p \to q) \land p) \to q \]

\[ ((p \to q) \land \neg q) \to \neg p \]

  1. Fallacies
    Affirming the consequent
    \(((p \to q) \land q) \to p\)
    Nageting the antecedent
    \(((p \to q) \land \neg p) \to \neg q\)
  2. Converse, Contrapositive, Inverse
    \(q \to p\)
    \(\neg q \to \neg p\)
    \(\neg p \to \neg q\)

    The fallacies are a product of assuming that the Converse and Inverse are equivalent to the conditional statement.

1.2.6. Bi-conditionals

It expressed a sufficient and necessary conditional relationship between two propositions. It is read as if and only if p, then q.

\[ p \Leftrightarrow q \]

This operator will return True only if both p and q have equal values. The expression can be represented with the 3 basic operators as:

\[ (p \to q) \land (q \to p) \equiv (\neg p \land \neg q) \lor (p \land q) \]

\[ p \equiv q = \neg (p \oplus q) \]

1.2.7. Order of Operators

  1. \(\neg\)
  2. \(\land\)
  3. \(\lor\)
  4. \(\to\)
  5. \(\Leftrightarrow\)

1.3. Equivalence

Two propositions are said to be equivalent only if both have equivalent truth tables.

\[ p \equiv q \]

1.3.1. Disjunctive Normal Form

It allows us to represent an un-known proposition by analyzing the truth table and constructing a new proposition using the 3 basic operators.

1.4. Morgan Laws

\begin{align} \neg (p \land q) \equiv \neg p \lor \neg q \\ \neg (p \lor q) \equiv \neg p \land q \end{align}

1.5. Logical Equivalences

1.5.1. Identity Laws

\[ p \land \top \equiv p \]

\[ p \lor \bot \equiv p \]

1.5.2. Denomination Laws

\[ p \lor \top \equiv \top \]

\[ p \land \bot \equiv \bot \]

1.5.3. Idempotent Laws

\[ p \lor p \equiv p \]

\[ p \land p \equiv p \]

1.5.4. Double Negation Law

\[ \neg ( \neg p) \equiv p \]

1.5.5. Commutative Laws

\[ p \lor q \equiv q \lor p \]

\[ p \land q \equiv q \land p \]

1.5.6. Associative Laws

\[ (p \lor q) \lor r \equiv p \lor (q \lor r) \]

\[ (p \land q) \land r \equiv p \land (q \land r) \]

1.5.7. Distributive Laws

\[ p \lor (q \land r) \equiv (p \lor q) \land (p \lor r) \]

\[ p \land (q \lor r) \equiv (p \land q) \lor (p \land r) \]

1.5.8. Morgan Laws

1.5.9. Absorption Laws

\[ p \lor (p \land q) \equiv p \]

\[ p \land (p \lor q) \equiv p \]

1.5.10. Negation Laws

\[ p \lor \neg p \equiv \top \]

\[ p \land \neg p \equiv \bot \]

1.6. Satisfiability

Any proposition is satisfiable if it is True for at least one case, that is, a proposition is satisfiable if its not a contradiction

2. Predicate Logic

It is away of breaking down a complex proposition into various parts. The way we go about this is by using Predicates and Quantifiers.

2.1. Predicates

A predicate is a statement which is similar to a proposition, but it is parametric.

\begin{array}{l} X \text{ is faster than me} \\ = \text{Subject} + \text{Predicate} \\ \to P(x) \end{array}

Once the parameters have been passed to the predicate, it becomes a proposition with an appropriate truth value. A predicate with \(n\) number of variables can be represented by:

\[ P(x_1, x_2, x_3, \ldots, x_n) \]

And once instantiated with variables:

\[ P(a_1, a_2, a_3, \ldots, a_n) \equiv p \]

2.1.1. Domains

Naturals \(\mathbb{N}\)
Integers \(\mathbb{Z}\)
Rationals \(\mathbb{Q}\)
Fractions of integers \(\{ \frac{p}{q} \vert p \in Z \land q \in Z \land q \ne 0 \}\)
Reals \(\mathbb{R}\)
All real numbers
Complex $\mathbb{C}
All complex numbers

2.2. Quantifiers

A quantifier expresses the truth value of a predicate, for its respective domain of variables. They add a modifier the predicate (for all, for many, for at least one, for none).

2.2.1. Universal Quantifier

\begin{array}{c} P(x) \text{ for all value of x within its domain} \\ \forall x P(x) \end{array}
We must show that \(P(x)\) holds true for all \(x\)
It is sufficient to show one value of \(x \vert \neg P(x)\)
If \(x\) is empty
the proposition will always be False
  1. Example

    If \(P(x) = x^2 > 0\) with the domain of \(x\) being all the reals, disprove \(\forall x P(x)\).

    To disprove this, we need to demonstrate one value for which it is false, in this case, that would be \(x = 0\) because \(0^2 = 0\)

2.2.2. Existential Quantifier

\begin{array}{c} P(x) \text{ for at least one value of x within its domain} \\ \exists x P(x) \end{array}
It is sufficient to show at least one value if \(x \vert P(x)\)
We must show that for all values of \(x\) it is true that \(\neg P(x)\)
If \(x\) is empty
the proposition will always be False.
  1. Example

    If \(P(x) = x = -x\) with the domain of \(x\) being all the reals, prove that \(\exists x P(x)\).

    The solution to proving an existential quantifier is done by demonstrating at least one value of x for which it holds true. In this case, that would be \(x = 0\) because \(0 = -0\). This can be done by logical thinking or by solving the equation \(x = -x\)

2.2.3. Exists Exactly One

This is a type of existential quantifier which allows for specification of the number of values for which the predicate is satisfiable.

\begin{array}{c} \text{There is exactly one } x \text{ such that } P(x) \\ \exists! x P(x) \end{array}

The definition for this is as follows:

\[ \exists x (P(x) \land \forall y (P(y) \Leftrightarrow x = y)) \]

We can generalize this to a specific number \(n\) for which the predicate is satisfiable.

\[ \exists_n x P(x) \]

2.2.4. Domain Restriction

We can also restrict the domain of a quantifier by adding conditions after the quantifier and before the predicate.

\begin{array}{l} \forall x > 0 P(x) \\ \exists x \ne 0 P(x) \end{array}

If we have a finite domain for which we are evaluating a predicate, we can easily evaluate the value by simply proving all the possibilities.

2.2.5. Quantifier Negation

If we want to negate a quantifier we must flip the outer quantifier and negate its inside.

\[ \neg \forall x P(x) \equiv \exists x \neg P(x) \]

\[ \neg \exists x P(x) \equiv \forall x \neg P(x) \]

2.2.6. Nested Quantifiers

If we have a predicate with more than 1 variables, we need n quantifiers to fully instantiate the predicate. For example, given a predicate with 2 variables, we can instantiate in the following way:

\[ \forall x \forall y P(x,y) \]

For nested quantifiers, the order matters, this can be seen in example 2.

\[ \exists x \forall y P(x,y) \not \equiv \forall y \exists x P(x,y) \]

  1. Example

    If \(P(x,y): x^2 + y^2 \ge 0\) with both \(x\) and \(y\) being reals, which of the following are true?

    1. \(\forall x \forall y P(x,y)\)
    2. \(\forall x \exists y P(x,y)\)
    3. \(\exists x \forall y P(x,y)\)
    4. \(\exists x \exists y P(x,y)\)

    Solution: The solution to this problem is intuitive because the predicate will hold true for any real, since both the parts of the sum will always be at lest 0.

  2. Example

    If \(P(x,y): x-y^2 = 0\) with both \(x\) and \(y\) being reals, which of the following are true?

    1. \(\forall x \forall y P(x,y)\) This one can be disproved with a counter-example where \(x=1, y=0\)
    2. \(\forall x \exists y P(x,y)\) For a negative x, the predicate will always be false since it will be a sum of \(x\) and \(y^2\).
    3. \(\exists x \forall y P(x,y)\) We can disprove this quantifier by solving the equation for x. \(x = y^2\) just does not make sense.
    4. \(\forall y \exists x P(x,y)\) This predicate is expression is true for two reasons, one is that for all values of \(y^2\) there will be some real value for \(x\). The other reason is that the order of the quantifiers is opposite to that in 3, therefore this one must be true.

3. Inference

Consists of an implication relationship between propositions called premises and one other called conclusion. We use a series of steps to demonstrate the implication of the premises. An example of this in natural language would be: If it rains, the street is wet. It rains. Therefore the street is wet.

  • We demonstrate the implication of premises
  • We have the propositions/steps to prove a conclusion

3.1. Arguments

3.1.1. Argument Validity

If an argument can establish some implication relationship between the premises and conclusion it is told to be valid.

  • A valid argument implies a tautology

If the inference is valid, then \(p_1 \land p_2 \land \ldots \land p_n \to q \equiv \top\)

3.1.2. Form

If an argument is valid or not, can only be determined using the logical form.

\begin{array}{r} p \to q \\ p \\ \hline \therefore q \end{array}

3.1.3. Soundness

Logic is not quite so concerned with soundness as it is with validity.

Sound Argument
An argument for which all premises are true and is valid
Un-sound Argument
An argument for which not all premises are true

3.2. Rules of Inference

An argument form which would generate a valid implication falls under the rules of inference

Recommended exercises for this topic can be found on pages 82 to 84 of the book

3.2.1. Modus Ponens

\begin{array}{r} p \\ p \to q \\ \hline q \end{array}
  1. If p is true, then q is true
  2. p is true
  3. Therefore q is true

3.2.2. Modus Tollens

\begin{array}{r} \neg q \\ p \to q \\ \hline \neg p \end{array}

3.2.3. Hypothetical Syllogism

\begin{array}{r} p \to q \\ q \to r \\ \hline p \to r \end{array}

3.2.4. Disjunctive Syllogism

\begin{array}{r} p \lor q \\ \neg p \\ \hline q \end{array}

3.2.5. Addition

\begin{array}{r} p \\ \hline p \lor q \end{array}

3.2.6. Simplification

\begin{array}{r} p \land q \\ \hline p \end{array}

3.2.7. Conjunction

\begin{array}{r} p \\ q \\ \hline p \land q \end{array}

3.2.8. Resolution

\begin{array}{r} p \lor q \\ \neg p \lor r \\ \hline \therefore q \lor r \end{array}

3.3. Rues of Inference for Quantified Propositions

3.3.1. Universal Instantiation

\begin{array}{r} \forall x P(x) \\ \hline \therefore P(c) \end{array}

3.3.2. Universal Generalization

\begin{array}{r} P(c) \text{ for an arbitrary c} \\ \hline \therefore \forall x P(x) \end{array}

3.3.3. Existential Instantiation

\begin{array}{r} \exists x P(x) \\ \hline \therefore P(c) \end{array}

3.3.4. Existential Generalization

\begin{array}{r} P(c) \text{ for an arbitrary c} \\ \hline \therefore \exists x P(x) \end{array}

3.4. Formal Proofs

A formal proof is a construction of a series of statements which are premises or logical inferences from previous statements. When writing a formal proof, we construct a table which in which we write the statement and next to it the explanation.

3.4.1. Example

\begin{align} (p \lor q) \to (r \land s) & \quad \text{Premise} \\ r \to t & \quad \text{Premise} \\ \neg t & \quad \text{Premise} \\ \neg r & \quad \text{Modus Tollens from 2 and 3} \\ (\neg p \land \neg q) & \quad \text{Modus Tollens from 4 and 1} \\ \neg p & \quad \text{Simplification of 5} \end{align}

3.5. Informal Proofs

An informal proof is a valid argument which established the truth of a mathematical statement.

  • We establish the truth of a statement
  • We do not have all the steps to prove a conclusion

3.5.1. Terminology

A statement we can prove using some axioms
A valid argument/set of arguments that demonstrate a theorem/proposition
Statements which are assumed to be true, they are in the most basic form
A small proof that is an element of another larger proof

3.6. Methods of Proof

Upon deciding which axioms to use, you then need to use some method of proof. The most common statements we will be proving are implications.

3.6.1. Direct Proof

We want to prove "If p, then q". This is done by assuming that the premise is true and then proving that the consequence is also true.

  1. We assume \(p\) to be true.
  2. By applying the laws of inference, we deduce \(q\) from \(p\).

3.6.2. Indirect: Proof by Contraposition

If we cannot arrive to the consequence using just the premise, we can use contraposition, which states that \((p \to q) \equiv (\neg q \to \neg p)\).

  1. We assume that \(\neg q\) is true
  2. We find a way to infer that \(\neg p\) is true
  3. Since this verifies the contrapositive, we have proved that \(p \to q\)

3.6.3. Indirect: Vacuous and Trivial proofs

If we are saying that \(p \to q\) is True, we can assume that:

  1. \(p\) is False (Vacuous proof)
  2. \(q\) is True (Trivial proof)

It is enough to prove just one of these (as long as we do not accept the premise being True) we can prove the condition to be True.

  1. Example

    If \(n\) is an integer and an even number, then \(2n\) must be an integer.

    Since an integer multiplied by another integer will also be an integer, we can say that \(q\) will be true. This is enough to prove that \(p \to q\) is also True.

3.6.4. Indirect: Proof by Contradiction

This can be used to demonstrate any statement \(p\). We say that \(\neg p\) implies a contradiction. A nicer way to think about this is by the following:

\[ \neg p \to \bot \equiv \neg (\neg p) \lor \bot \equiv p \lor \bot \equiv p \]

  1. Example

    Show that \(\sqrt{2}\) is an irrational number.

    An irrational number is a fraction of 2 integers. We assume that \(\sqrt{2}\) is rational. This would mean that \(\sqrt{2} = \frac{p}{q}\) where both \(p,q\) are integers. The key thing to assume here is that the fraction is in its smallest form. From the previous equation we can get to \(p^2 = 2q^2\) which tells us that \(p\) is an even number (if the square of a number even, then so is that number$). Further, we can also come to the conclusion that \(q\) is even. Since both \(p,q\) are even, the fraction is not its simplest form - implying a contradiction.

3.6.5. Proof by Cases

This is a proof which can be used a used as a part of another proof when proving implications. If we have an implication where the premise consists of disjunctions, we can apply the following:

\begin{align} (p_1 \lor p_2 \lor \ldots \lor p_n) \to q \\ (p_1 \to q) \land (p_2 \to q) \land \ldots \land (p_n \to q) \end{align}

This proof is very helpful when we want to prove that a condition is satisfiable for a group of elements.

  1. Example

    Prove that if \(n\) is not a multiple of 3, \(2n\) is not a multiple of 3.

    To define a value as not a multiple of 3, we have two formulas \(n = 3k + 1 \quad n = 3k + 2\). We can reformulate the proposition by saying \((n = 3k+1) \lor (n = 3k^\prime) \to \neg (2n = 3k^{\prime\prime})\). We then have to show that both cases imply the consequence.

3.6.6. Equivalence Proof

As previously mentioned \(p \leftrightarrow q = p \equiv q\), so if we want to prove some equivalence, we can use \((p \to q) \land (q \to p)\).

3.6.7. Existential Statements Proof

We have two strategies for this.

Constructive Proof
We show an example that verifies a predicate and apply existential generalization to prove the proposition.
Non Constructive Proof
We show that there exists an element which validates the predicate but we dont specify which one. This is most commonly proof by contradiction.

3.6.8. Universal Statements Proof

We show that a predicate holds for an arbitrary value and then apply universal generalization.
To disprove a universal statement we need to find a counterexample. This action is a process of negation, making the US an ES.

3.6.9. Strategy for Proofs

So what the fuck should you use? It comes down to trial and error, but also practice and intuition.

Trial and error
If direct proof doesnt work, try indirect lol.
Complex propositions
If there are complex propositions in an implication, they quite possibly can be negated, allowing use to use an indirect method.
Using proof by contradiction with conditional statements
We show that \(\neg (p \to q)\) implies \(\bot\).
Proof by cases
Yeah… no.

4. Set Theory

4.1. Sets

The definition of a set is a collection of unordered unique objects. Each object in that set is a member.

\(a\) is a member of \(A\)
\(a \in A\)
\(a\) is not a member of \(A\)
\(a \not\in A\)

We can define a set in various way. We can list all its elements or skip some obvious elements. If our set were to consist of a larger number of objects, listing them all is impractical, to overcome this we can use predicates.

\begin{array}{c} x \text{ such that } P(x) \\ A = \{ x \vert P(x)\} \end{array}

4.1.1. Logical Definition

The way we can express a set by using logic is with the following expression:

\[ \forall x ((x \in A) \Leftrightarrow P(x)) \]

4.1.2. Interval Definition

A very common way to define a set is to use an interval such as \((a,b) \quad [a,b) \quad (a,b] \quad [a,b]\). in this notation the meaning of the parenthesis and bracket is open and closed interval respectively.

4.1.3. Equal Sets

The set \(A\) is equal to \(B\) if and only if all the elements of \(A\) are also elements of \(B\).

\[ (A = B) \Leftrightarrow \forall x (x \in A \Leftrightarrow x \in B) \]

\[ (A = B) \Leftrightarrow (A \subseteq B) \land (B \subseteq A) \]

We need to give a counterexample, this can be represented by \(\exists x (x\in A \oplus x \in B)\)

4.1.4. Important Sets

Sets as Elements
A set can also be an element of a set
Empty Set \(\emptyset\)
The empty set is a set with no elements in it. \(\emptyset \ne \{\emptyset\}\)
Universal Set U
A set containing all elements under consideration

4.2. Subsets

The set \(A\) is a subset of \(B\) if and only if all elements of \(A\) are also elements of \(B\). If this is so, \(B\) is the superset of \(A\).

\[ A \subseteq B \]

\[ \forall x ((x \in A) \to (x \in B)) \]

It is true for every set that it has at least 2 subsets, the empty set and itself.

\[ \forall X ((X \supseteq \emptyset) \land (X \supseteq X)) \]

Finally, if a set \(A\) is a subset of \(B\) but they are not equal, we say that \(A\) is proper subset of \(B\).

4.3. Set Cardinality

The cardinality of a set is the number of elements in that set. This is represented by \(\vert A \vert\). If a set has infinite elements, its cardinality is infinity.

4.4. The Power Set

A power set is a set of all the subsets of \(A\). If \(A\) is a finite set, the cardinality of the power set will be given by \(2^n\) where \(n = \vert A \vert\)

Given that \(A = \{a,b,c\}\)
The power set of \(A\) is \(P(A) = \{\emptyset, \{a\}, \{b\}, \{c\} \{a, b\} \{a,c\} \{b,c\}\{a,b,c\} \}\)

4.5. Cartesian Product

In discrete mathematics, an ordered collection is called a relation. If we have two sets, \(A,B\) each with a different cardinality, the Cartesian product of these two sets is a set of all possible two-term relations that can be constructed using the two sets.

\[ A \times B = \{(a,b) \vert ((a \in A) \land (b \in B))\} \]

If the sets used for a Cartesian product are all finite, the cardinality of the Cartesian product for \(n\) sets will be as follows:

\[ \vert A_1 \times A_2 \times \ldots \times A_n \vert = \vert A_1 \vert \times \vert A_2 \vert \times \ldots \times \vert A_n \vert \]

4.6. Set Operations

4.6.1. Union

The union operator produces a new set of elements which are both in set \(A\) and \(B\).

\[ \forall ((x \in A \cup B) \Leftrightarrow ((x \in A) \land (x \in B)) \]

\[ A \cup B = \{x \vert (x \in A) \lor (x \in B)\} \]

\(\vert A \cup B \vert = \vert A \vert + \vert B \vert - \vert A \cap B \vert\)

4.6.2. Intersection

The intersection produces a set of elements which are only in set \(A\) and \(B\) at the same time.

\[ \forall x (( x \in A \cap B) \Leftrightarrow ((x \in A) \land (x \in B))) \]

\[ A \cap B = \{x \vert (x \in A) \land (x \in B)\} \]

4.6.3. Subtraction

When subtracting two sets, the difference will consist of all elements in \(A\) that are not in \(B\).

\[ \forall x ((x \in A - B) \Leftrightarrow ((x \in A) \land (x \not \in B))) \]

\[ A - B = \{x\vert(x \in A) \land (x \not \in B)\} \]

\(\vert A - B \vert = \vert A \vert - \vert A \cap B \vert\)

4.7. Complementary Set

This is a set of all elements in the sample space that are not in \(A\).

\[ \bar{A} = U - A = \{ x \vert (x \in U ) \land (x \not \in A)\} \]

\[ \bar{A} = \{ x \vert x \not \in A\} \]

4.8. Logic and Set Equivalences

For sets, we can apply almost any logical transformation assuming the following:

\begin{array}{l} A \cup B \sim p \lor q \\ A \cap B \sim p \land q \\ \bar{A} \sim \neg p \end{array}

This is due to the role of predicates in the definition of sets.

\[ A = \{ x \vert P(x)\} \]

5. Functions

A function is an assignment of a single value \(b\) in \(B\) for every value \(a\) in \(A\). A function is also refereed to as a mapping, transformation or black box (possibly and oracle).

\begin{array}{l} f(a) = B \\ f : A \to B \end{array}

What makes a function a function? The relationship can be described with the following expression:

\[ \forall a \in A \exists ! b \in B (f(a) = b) \]

Why would some assignments not be functions?
Not all elements in \(A\) are assigned a value in \(B\). Some values in \(A\) are assigned more than one value in \(A\). TLDR: Some element in \(A\) doesnt have a value or it has multiple

5.1. Domain, Codomain and Range

If \(f(a) = b\) we call \(b\) the image of \(a\) and vice versa \(a\) is the preimage.

The set \(A\)
The set \(B\)
The set of all images for all values of \(A\)

5.2. One to One Functions

A function is said to be one to one or injective if for every value \(b\) there is at most one value \(a\).

\[ \forall a \in A \forall b \in B ((f(a) = f(b)) \Leftrightarrow (a = b)) \]

How can we tell if a function is injective?
As per the definition, above we use two different variables and test that if \(f(a) = f(b)\) it must be, that \(a = b\), if this is so, the function is injective.

5.3. Onto Functions

A function is onto or surjective if and only if for each value in \(B\) there is at least one value in \(A\)

\[ \forall b \in B \exists a \in A(f(a) = b) \]

How can we tell if a function is onto?
We define some arbitrary image of the function as \(c\) and then solve for \(x\). If we have \(f(x) = \sqrt{x}\) we then proceed to insert the image \(c = \sqrt{x} \Rightarrow x = c^2\). Since for a square, the range is only positive reals, this is not an onto.

5.4. Composite Functions

A common expression to denoted nested or composed function is the following: \[ (f \circ g) (x) = f(g(x)) \] In this scenario the value returned by g is then the input for f.

  • If the co-domain of the inside function is not a subset of the domain of the outer function, the composition will not be defined.

5.5. Partial Functions

This is a function which has certain points or ranges which cannot be a part of the domain.

6. Sequences

A sequence is a collection of elements which can be intuitively continued by knowing the first terms. in broader terms, a sequence assigns some order or pattern represented by some index - Therefore, it is a function. We use \(a_n\) to represent the image of \(n\).

6.1. Arithmetic Progression

In its most abstract form, it is a linear function. Commonly represented in sequence form as:

\[ a, a + d,a + 2d, \ldots, a + nd, \ldots \]

\[ a_n = a + dn \]

It is composed of an initial term(\(a\)) and common difference(\(d\)).

6.2. Geometric Progression

This progression is of exponential form. It is composed of an initial term (\(a\)) and common ration (\(r\)).

\[ a, a * r, a*r^2, ... , a * r^n \]

\[ a_n = ar^n \]

6.3. Recurrence Relation

A recurrent relation is a rule which defines a value for the nth term as a function of some previous terms. The implicit formula for a recurrent relationship is called a closed formula, it is the solution to given relation.

  • To find the closed formula, we should use iteration to see a pattern in the sequence.

7. Summations

A summation is defined as the sum of all the terms of the sequence between \(i,n_0\) and \(n_f\), including both. The summation term is defined by $∑i=0n, where \(i\) is the initial term and \(n\) the final.

7.1. First \(n\) Integers Sum

\[ \sum_{i=1}^{n}{i} = \frac{n(n+1)}{2} \]

7.2. Other Rules

\[ \sum_{n=s}^t {C * f(n)} = C * \sum_{n=s}^{t} {f(n)} \]

\[ \sum_{n=s}^{t} {f(n)} = \sum_{n=s+p}^{t+p} {f(n-p)} \]

\[ \sum_{i=0}^{n-1} {a^i} = \frac{1-a^n}{1-a} \]

7.3. Nested Summations

If we have an expression where there are two sums \(\sum\sum\), we expand the far right summation and include it in the second sum.

  1. Example

    Calculate \(\sum_{i=1}^2 \sum_{i=1}^3 ij^2\)

    \(\sum_{i=1}^2 \sum_{i=1}^3 ij^2 = \sum_{i=1}^2(i + 4i + 9i) = (1+4+9) + (2+4*2+9*2)\)

Author: Daniel Rosel

Created: 2022-10-30 Sun 22:35