Addition and Simplification Laws

In logic the addition law and simplification law are sometimes misused.

Law of Addition

\(p \rightarrow p \vee q\)

This law states that if a proposition \(p\) is known to be true then the disjunction of  \(p\) with any other proposition will also be true.

Law of Simplification

\([(p) \wedge (q)] \rightarrow p \)

also,

\([(p) \wedge (q)] \rightarrow q \)

This law states that if the conjunction of \(p\) and \(q\) is true then we can deduce \(p\) is true. Similarly, we can deduce \(q\) is true. Remember that \([(p) \wedge (q)]\) is true only if both propositions \(p\) and \(q\) are true. That's why we can deduce \(p\)  is true and that \(q\) is true.

Some students attempt to apply the law of simplification to a disjunction. Without knowing the truth values of \(p\) and \(q\) some students may deduce from the statement \( p \vee q\) that \(p\) is true or that \(q\) is true. This is not valid. From \( p \vee q\) we know that at least one of the propositions is true, but we do not have enough information to know which one of them is true.

Finding a Formula when Solving Recurrence Relations using Induction

Induction is a popular technique for solving recurrence relations that involves guessing the formula instead of deriving it through computation. Induction is then used to prove that the formula found by conjecture is valid for the given recurrence relation.

Some people have a natural gift for noticing patterns in numbers and may actually conjecture the formula with ease. Others may struggle with this approach at first but after practising with a variety of problems may discover that finding the formula can be an almost enjoyable task.

Tips for finding the formula:

1. List about 3-5 iterations of the relation. On your first pass, don't sum or calculate products or simplify the expression. The pattern may be easier to see with the expression in this form. If no pattern is obvious, then simplify.
2. Identify which values remain constant in each iteration.
3. Identify which values change with each iteration.
4. Do you notice a sum of values? A product? Is the product some value raised to an exponent/power?
5. Identify the relationship between the number of the iteration and the changing values.

Example:

Suppose we would like to find a recurrence relation for \(s_0 = 3, s_k = s_{k-1} + 2k\) for all integers \(k >=1\)

\(s_0 = 3\)
\(1^{st}\) iteration:  \(s_1 = 3 + 2.1\)
\(2^{nd}\) iteration: \(s_2 = 3 + 2.1 + 2.2\)
\(3^{rd}\) iteration: \(s_3 = 3 + 2.1 + 2.2 + 2.3\)

From this we can see that the first term, 3, remains constant and 2 is a factor of the remaining terms. So we get

\(s_0 = 3\)
\(1^{st}\) iteration:  \(s_1 = 3 + 2(1)\)
\(2^{nd}\) iteration: \(s_2 = 3 + 2(1 + 2)\)
\(3^{rd}\) iteration: \(s_3 = 3 + 2(1 + 2 + 3)\)

The values inside the brackets change on each iteration and here we have a sum of terms. But how do we generalise? Well we look for a relationship between the number of the iteration and our changing values. In this example, in our \(k^{th}\) term we have 1 + 2 + ...+ k. This is the sum of an arithmetic sequence where a = 1 and d = 1. The sum of the first k terms in an arithmetic sequence is given by \(\frac{k}{2}(2a + (k-1)d)\).
Since a = 1 and d = 1 then. \(1 + 2 + ... + k = \frac{k(k+1)}{2}\)

So our final solution is
\(s_n = 3 + 2 \frac{n(n+1)}{2}\)
\(s_n = 3 + n(n+1)\)

Depending on the complexity of the recurrence relation you may not be able to conjecture a formula easily but there are methods for solving recurrence relations that involve identifying the type of recurrence relation and using an appropriate known closed-form formula.See this article for more details.