How many Solutions of x + y + z = k

In this post we will consider all the positive integer solutions of the equation x + y + z = k. At the end of the post we will generalize the method.

Let us first solve the equation. There is a x, a y and a z. We can consider x 1's, y 1's and z 1's. So there are a total of (x + y + z) 1's. We can find its integer solutions by separating  1's at different positions. Consider the equation x + y + z = 9.

Some of the solutions of the equation are

11|111|1111 (2+3+4)
111|111|111 (3+3+3)
1111|111|11 (4+3+2)
1111|11|111 (4+2+3)
11|11|11111 (2+2+5)

Add all the ones in one group separated by |. The number of solutions of this type is the solution of the equation x + y + z = 9. The number of solutions of the equation is (9+2)!/(9!2!) = (11×10)/2 = 55. Hence there are 55 solutions. If we have the total as k and the number of plus sign is n. Then the total number of solutions is (k+n)!/(k!n!). This can be written in the combination symbol as C(n+k,k).

This equation is similar as taking the combination of r things in n containers of similar kind. The number of combinations is (n+r−1)!/(n−1)!r!. This can be written in the combination symbol as C(n+r−1,r).

Recurrence relation (Part 2) : Linear Equations

In the post Recurrence Relation (Part 1) we studied three examples of recurrence relations. In this post we will solve them. The recurrence relation (T_n = T_n-1 + T_n-2) of Fibonacci problem is linear and has order 2 and degree 1. It is also homogeneous. The recurrence relation (T_n = 2T_n-1 + 1) of Tower of Hanoi problem is also linear. It has order 1 and degree 1 but it is non homogeneous. Recurrence relations can exist in many forms as linear or non-linear.

A linear recurrence relation looks like this

T_n = f₁(n)T_n-1 + f₂(n)T_n-2 + f₃(n)T_n-3 + ...+ f_r(n)T_n-r+...+f_n-1(n)T₁ + f(n)
The order of the recurrence relation is r if f_i(n) = 0 for i > r.
It is called homogeneous if f(n) = 0 and non-homogeneous if f(n) ≠ 0.
We will consider linear homogeneous and non-homogeneous recurrence relation with constant coefficients. A linear recurrence relation with constant coefficients is given by

T_n = C₁T_n-1 + C₂T_n-2 + C₃T_n-3 + ...+ C_rT_n-r+...+C_n-1T₁ + f(n) where C_i is a constant, 0 < i < n.
The order of the recurrence relation is r if C_i = 0 for i > r.
It is called homogeneous if f(n) = 0 and non-homogeneous if f(n) ≠ 0.

---

We will solve the linear homogeneous recurrence relation with constant coefficients first. The example of this type of equation which we are going to solve is Fibonacci Problem.
T_n = T_n−1 + T_n−2
Substitute the Terms with the r^{(the subscript)}
We get,
rⁿ = rⁿ⁻¹ + rⁿ⁻²
Divide throughout by the lowest power term which is r^n-2.
We get,
r² = r + 1
r² − r − 1 = 0
The above equation is called the characteristic polynomial of the recurrence relation and its roots are called characteristic roots.
The solution of the polynomial is r₁ = (1 + √5)/2 and r₂ = (1 − √5)/2

The solution of the recurrence relation can be written like this
T_n = A(r₁)ⁿ + B(r₂)ⁿ = A[(1 + √5)/2]ⁿ + B[(1 − √5)/2]ⁿ

T₁ = 1 = A[(1 + √5)/2] + B[(1 − √5)/2] = (A + B)/2 + (√5)/2(A − B)
T₂ = 1 = A[(1 + √5)/2]² + B[(1 − √5)/2]²
= A [1 + 5 + 2√5]/4 + B [1 + 5 − 2√5]/4
= A [6 + 2√5]/4 + B[6 − 2√5]/4

We get two relations
(A + B) + (√5)(A − B) = 2 ----(i)
and
3(A + B) + (√5)(A − B) = 2 ----(ii)

Solving the equations simultaneously, we get
3(i) - (ii)
2√5(A − B) = 4
A − B = 2/√5 and substituting in (i)  we get
A + B = 0

Again solving simultaneously,
2A = 2/√5
A = 1/√5
B = -1/√5
Hence the solution of the recurrence is
T_n = [1/√5][(1 + √5)/2]ⁿ - [1/√5][(1 − √5)/2]ⁿ

---

Next we will solve the recurrence relation T_n = 2T_n−1 + 1 which belongs to the tower of Hanoi problem.

Linear non homogeneous recurrences require us to solve for their homogeneous part then substitute a relation which satisfies the non homogeneous recurrence. There are many methods which are different from it and can be used to solve many recurrences. These methods are

1. Method of iteration
2. Method of substitution
3. Method of telescoping sums
4. Method of inspection

Here, we will use method of iteration to solve the recurrence.
In this method we substitute the earlier term in the recurrence and look at the pattern and solve the series.
T_n = 2T_n−1 + 1
T_n = 2(2T_n−2 + 1) + 1
T_n = 2(2(2T_n−3 + 1) + 1) + 1
As T₁ = 1, so we get
T_n = 2^n-1 + 1 + 2 + 2² +....+ 2^n-2
T_n = 2^n-1 + (2^n-1 − 1) = 2ⁿ − 1

---

Now we will solve the recurrence T_n = T_n-1 + k. This problem is multiplication problem. This recurrence will be solved by inspection. In inspection we write down enough terms such that we can guess the solution.
T₁ = k. Hence,
T_n  = T_n−2 + k + k
T_n  = T_n−3 + k + k + k
T_n  = T_n−4 + k + k + k + k
We can guess the solution to be T_n = nk as the number of k's increases as we use the lower terms of the recurrence and it increases by a definite number..

Recurrence Relation (Part 1)

In mathematics we come across many series which can be expressed in terms of its some or every term. These terms can be distributed in the whole of the series. For example if the n^th term is termed as T_n and it depends on its previous two terms then T_n can be expressed as many recurrence relation with these two terms. One of it is T_n = T_n-1 + T_n-2. Recurrence relations are used in computer science to find the time complexity of many algorithms. Let us consider some examples of recurrence relations. We will solve them in some other post.

• Multiple by consecutive numbers: Look at the series 2,4,6,8,10,12,14,16...The series can be represented as 0+2, 2+2, 4+2, 6+2, 8+2, 10+2, 12+2, 14+2...Here every term can be represented as sum of the previous term and 2.Hence, multiplication of 2 and consecutive natural numbers can be represented like this. T_n = T_n−1 + 2 where the first term is T₁ = 2. Similarly, multiplication of can be represented like T_n = T_n−1 + k where T₁ = k.



• Fibonacci Series: Leonardo di Pisa also known as Fibonacci posed a problem about rabbits in his book Liber Abaci in 1202. The problem stated: One pair of rabbits, one male and one female, are left on an island. These rabbits begin breeding at the end of two months and produce a pair of rabbits of opposite sex at the end of each month thereafter. Can you determine the number of pairs of rabbits after n months assuming no rabbit dies on this island?
  
  Let us try to solve this problem. In first month there is one pair. So, T₁ = 1. In the second month there is one pair. So, T₂ = 1. In the third month there are two pairs. So, T₃ = 2. Two are the rabbits in the first month and additional two are due to birth. In fourth month the pair of children produced are equal to the pairs of rabbits in the second month which can produce, this is equal to 1. The additional number of pairs are those in third month which equals 2. So, T₄ = 3. So it can be expressed in the recurrence relation as T_n = T_n-1 + T_n-2. Where T_n, T_n-1 and T_n-2 is pair of rabbits in n^th, n-1^th and n-2^th month respectively.


• The tower of Hanoi: The problem is invented by Edouard Lucas in 1883. We are given a tower of eight discs, initially stacked in decreasing size on one of three pegs. The problem is to transfer the entire tower to one of three pegs, moving only one disc at a time without ever moving a larger disc onto a smaller one.
  
  Let us solve this problem.
  
  
  
  1. With one disk we can move it in 1 move. So T₁ = 1.
  2. With two disks we can move it in 3 moves. The procedure is like this. There are three pegs A, B and C. A has both the disks in increasing order from top arranged in the order 2,1. We move 1 to B. Then move 2 to C. Then move 1 to C. So the number of moves for two disks is three. So, T₂ = 3.
  3. For three disks, we can move it in 7 moves. The procedure is like this. There are three pegs A, B and C. A has all the three disks in increasing order from top arranged in the order 3,2,1. We, move 1 to C, move 2 to B, move 1 to B, move 3 to C, move 1 to A. Then move 2 to C. Then move 1 to C. So the number of moves for three disks is seven. So, T₃ = 7.
  We can generalize the procedure like this, move n−1 disks to one peg then move the n^th disk and bring back the n−1 disks above the n^th disk. We can solve this problem in T_n = 2T_n-1 + 1 moves.

Read solutions of the above recurrences

Whether this or this or both or none (Logical connectives)

This post deals with propositional calculus. In propositional calculus we deal with propositions. Propositions are those sentences which are either true of false. One and the most important thing which is required in propositional calculus is reasoning. Our ancestors were able to form civilizations as they were able to reason things. But a rigorous study of logical reasoning was not done for a long time. The first such study that has been found is by the Greek philosopher Aristotle (384-322 BC). Leibnitz (1646-1716) and George Boole (1815-1864) seriously studied this and came up with with a theory and called it symbolic logic.

'The sun rises in the East.' is a proposition. It is a proposition because it can only take two values either true or false. The sentences which are either true or false are propositions or statements. In mathematics we come across many propositions and statements. x>2 is not a proposition as it can be true or false according as x>2 or x<2. So, 2<3 is a proposition but x<2 is not a proposition.

There are three main connectives in propositional calculus. It is conjunction(∧), disjunction(∨) and negation(¬).

Consider the two statements.
p: I play badminton.
q: I play football.

We can frame two statements with the combination of A and B. It is called compound statement.

I play badminton and I play football.

The above statement is formed by the combination of the two statements with the help of 'and'. This is called conjunction. It is denoted by the symbol '∧'. We can frame a table of all the possibilities. It is called truth table.
 

F is false. T is true.
p	q	p∧q
F	F	F
F	T	F
T	F	F
T	T	T

As we can see from the above that conjunction is true only when all the possibilities are true and false if anyone is false.

I play badminton or I play football.

The above statement is formed by the combination of the two statements with the help of 'or'. This is called disjunction. It is denoted by the symbol '∨' We can frame a truth table of all the possibilities.
 

F is false. T is true.
p	q	p∨q
F	F	F
F	T	T
T	F	T
T	T	T

As we can see from the above that conjunction is false only when all the possibilities are false and true if anyone is true.

I don't play football.

The statement 'I play football.' is transformed to 'I don't play football.' with the help of 'negation'. It is denoted by '¬'. The truth table for 'negation' is

F is false. T is true.
q	¬q
F	T
T	F

Negation of q is true when q is false and false when q is true.