Solution of Recurrence Relation

Step 1 - Given data

• Recurrence: $a_n = 5a_{n-1} - 6a_{n-2}$
• Initial conditions: $a_1 = 1$, $a_2 = 2$

This is a linear homogeneous recurrence of degree 2 with constant coefficients.

Step 2 - Solve

Characteristic equation

Substitute $a_n = r^n$:

$$r^2 = 5r - 6 \implies r^2 - 5r + 6 = 0$$

Factor:

$$(r-2)(r-3) = 0 \implies r_1 = 2,\ r_2 = 3$$

Distinct roots, so the general solution is:

$$a_n = \alpha_1 \cdot 2^n + \alpha_2 \cdot 3^n$$

Apply initial conditions

For $a_1 = 1$: $$2\alpha_1 + 3\alpha_2 = 1 \quad (i)$$

For $a_2 = 2$: $$4\alpha_1 + 9\alpha_2 = 2 \quad (ii)$$

Multiply $(i)$ by 2: $$4\alpha_1 + 6\alpha_2 = 2 \quad (iii)$$

Subtract $(iii)$ from $(ii)$: $$3\alpha_2 = 0 \implies \alpha_2 = 0$$

From $(i)$: $$2\alpha_1 = 1 \implies \alpha_1 = \tfrac{1}{2}$$

Final solution

$$\boxed{a_n = \tfrac{1}{2}\cdot 2^n = 2^{n-1}}$$

Verification

The solution satisfies both the recurrence and initial conditions.

Euler Path, Hamilton Path, and Hasse Diagram

Part 1: Euler Path and Hamilton Path

Euler Path

Definition: An Euler path is a walk in a graph that traverses every edge exactly once (vertices may repeat). If it starts and ends at the same vertex, it is an Euler circuit.

Existence condition: A connected graph has an Euler path iff it has exactly 0 or 2 vertices of odd degree (2 odd-degree vertices give an open Euler path; 0 gives an Euler circuit).

Example:

Vertices ${A,B,C,D}$, edges: $A\text{-}B,\ B\text{-}C,\ C\text{-}D,\ D\text{-}A,\ A\text{-}C$.

Degrees: $\deg(A)=3,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=2$. Two odd-degree vertices $(A,C)$, so an Euler path exists:

$$A \to B \to C \to D \to A \to C$$

This uses each of the 5 edges exactly once.

Hamilton Path

Definition: A Hamilton path is a path that visits every vertex exactly once. If it returns to the starting vertex, it is a Hamiltonian circuit (cycle).

Note: There is no simple necessary-and-sufficient condition for a Hamilton path (unlike Euler paths).

Example: Same graph as above:

$$A \to B \to C \to D$$

visits all 4 vertices exactly once, so it is a Hamilton path.

Key Difference

Part 2: Hasse Diagram for Divisibility on ${1,2,5,8,16,32}$

Step 1: Divisibility relations (a | b)

• $1 \mid$ everything
• $2 \mid 8,\ 2 \mid 16,\ 2 \mid 32$
• $8 \mid 16,\ 8 \mid 32$
• $16 \mid 32$
• $5$: divides nothing else in the set (since $8,16,32$ are not multiples of 5)

Step 2: Cover relations (remove transitive edges)

• $1 \lessdot 2$, $1 \lessdot 5$
• $2 \lessdot 8$ (since $4 \notin$ set)
• $8 \lessdot 16$
• $16 \lessdot 32$

Step 3: Hasse Diagram

        32
        |
        16
        |
        8
        |
        2       5
         \     /
            1

Step 4: Maximal, Minimal, Greatest, Least

Minimal element: element with nothing below it. $1$ is the only minimal element.

Maximal elements: elements with nothing above them. $32$ (top of chain) and $5$ (dead-end, divides nothing else). $$\text{Maximal} = {5,\ 32}$$

Least element: divides every element $\Rightarrow$ $1$ divides all. $$\text{Least} = 1$$

Greatest element: must be divisible by all others. $32$ is not divisible by $5$, and no single element is above all others $\Rightarrow$ no greatest element.

Summary Table

For the Hasse diagram the minimal element is ${1}$, the maximal elements are ${5,32}$, the least element is $1$ and there is no greatest element. On the Euler path, a route such as $A \to B \to C \to A \to D \to C$ is invalid because it repeats an edge and skips another; the valid path is $A \to B \to C \to D \to A \to C$. The Euler condition should also include the "0 odd vertices" case for completeness.

Applications of Conditional Probability and Combination Problem

Given Data

• Total families available: $n = 9$
• Families to be invited: $r = 6$
• Order does not matter (a set of invitations), so this is a combination problem.

Part 1: Two Applications of Conditional Probability

Conditional probability $P(A|B)$ is the probability of event $A$ occurring given that event $B$ has already occurred. Two applications:

1. Medical Diagnosis: Determining the probability that a patient actually has a disease given a positive test result, i.e., $P(\text{Disease} \mid \text{Positive Test})$. This is often computed using Bayes' theorem.

2. Spam Email Filtering: Classifying an email as spam given the presence of certain words, i.e., $P(\text{Spam} \mid \text{Keywords})$. Bayesian spam filters rely on this.

(Other valid examples: weather forecasting, risk assessment in insurance, fault diagnosis in machines.)

Part 2: Combination Problem

Formula

The number of ways to choose $r$ families from $n$ families, without regard to order:

$$C(n, r) = \binom{n}{r} = \frac{n!}{r!,(n-r)!}$$

Solution

$$C(9, 6) = \frac{9!}{6!,(9-6)!} = \frac{9!}{6!,\cdot,3!}$$

Expanding and cancelling $6!$:

$$= \frac{9 \times 8 \times 7 \times 6!}{6! \times (3 \times 2 \times 1)} = \frac{9 \times 8 \times 7}{6} = \frac{504}{6} = 84$$

Conclusion

There are $\boxed{84}$ different sets of invitations that could be written when choosing 6 families out of 9.