Q.If $X = \{8^n - 7n - 1 \mid n \in \mathbb{N}\}$ and $Y = \{49n - 49 \mid n \in \mathbb{N}\}$. Then
(A) $X \subset Y$
(B) $Y \subset X$
(C) $X = Y$
(D) $X \cap Y = \phi$

Concept: Set inclusion via divisibility

We need to determine the relationship between sets $X$ and $Y$ by examining their elements.

Step 1: Characterize set $Y$.

So $Y$ consists of all non-negative multiples of $49$.

Step 2: Check if elements of $X$ are multiples of $49$.

We claim $8^n - 7n - 1 \equiv 0 \pmod{49}$ for all $n \in \mathbb{N}$.

For $n = 1$: $8^1 - 7(1) - 1 = 0 \in Y$ ✓

For $n = 2$: $8^2 - 7(2) - 1 = 64 - 14 - 1 = 49 \in Y$ ✓

Step 3: Prove by induction that $49 \mid (8^n - 7n - 1)$ for all $n \geq 1$.

Base case ($n=1$): Already verified.

Inductive step: Assume $8^k - 7k - 1 = 49m$ for some $m \in \mathbb{N}$.

Thus every element of $X$ is a multiple of $49$, so $X \subseteq Y$. …

Understanding the sets

Set $X$ collects numbers of the form $8^n - 7n - 1$ for natural numbers $n$, while $Y$ collects all multiples of $49$ (since $49n - 49 = 49(n-1)$ ranges over all multiples as $n$ varies). The question asks about their relationship.

The key insight: if we can prove that $8^n - 7n - 1$ is always divisible by $49$, then every element of $X$ belongs to $Y$, establishing $X \subset Y$. Conversely, we need to check whether every multiple of $49$ can be expressed in the form $8^n - 7n - 1$.

Proving divisibility by $49$

We claim that $8^n - 7n - 1 \equiv 0 \pmod{49}$ for all $n \in \mathbb{N}$.

Step 1: Rewrite $8 = 7 + 1$, so $8^n = (7+1)^n$. By the binomial theorem:

Step 2: Substitute into $8^n - 7n - 1$:

Step 3: Factor out $7^2 = 49$:

Since the expression in parentheses is an integer, $49 \mid (8^n - 7n - 1)$ for all $n \in \mathbb{N}$.

Checking the reverse inclusion

Does $Y \subset X$? In other words, can every multiple of $49$ be written as $8^n - 7n - 1$ for some $n$?

Let's compute the first few elements of $X$: