Given two specific sets, show that one is a subset of another

Question

Given $$X = \{x : x = 4^n-3n-1 ; n\in\mathbb{N}\}$$ and $$Y = \{y : y = 9(n-1); n\in\mathbb{N}\}$$ Prove that $X \subset Y$.

I've been struggling with this problem for hours but I couldn't find a solution. All I could figure out is that when I put the same value of $n$ in the condition of both sets (as a bound), the elements of set become the same. e.g When I put $n = 1$, I get $X = \{0\}$ and $Y = \{0\}$. But I need a valid proof for it.

Answer 1

Zain Patel's answer outlines what kind of argument you really to construct: an induction argument. The general flow of the inductive proof will be like so:

Fix some $k\geq 1$ and assume that $$ P(k) : 4^k-3k-1=9\ell\qquad(\ell\in\mathbb{Z}) $$ holds. To be shown is that $$ P(k+1) : 4^{k+1}-3(k+1)-1=9\eta\qquad(\eta\in\mathbb{Z}) $$ follows. Starting with the right-hand side of $P(k+1)$, \begin{align} 4^{k+1}-3(k+1)-1 &= 4(4^k-3k-1)+9k\tag{rearrange}\\[0.5em] &= 4(9\ell)+9k\tag{by the inductive hypothesis}\\[0.5em] &= 9(4\ell+k)\tag{factor out the $9$}\\[0.5em] &= 9\eta\tag{$4\ell+k=\eta\in\mathbb{Z}$} \end{align} we end up at the right-hand side of $P(k+1)$, completing the inductive proof.

This is all you really need to show.

Answer 2

Hint: Show that $4^n -3n -1$ is divisible by $9$ for all positive $n$, ring a bell here? Induction.

The base case is obviously divisible by $9$. Assume that $f(k) = 4^k - 3k - 15$ is divisible by $9$ so that $f(k) = 9l$ for some $l \in \mathbb{Z}$.

Can you continue from there?

And since $Y$ is the set of multiples of $9$, $X \subset Y$... the result follows.

Answer 3

$$4^k-3k-1=(3+1)^n-3n-1\\ [\binom{n}{0}3^n!^0+\binom{n}{1}3^{n-1}1^0+...+\binom{n}{n-2}3^21^{n-2}+\binom{n}{n-1}3^11^{n-1}+\binom{n}{n}3^01^{n} ]-3n-1=\\3 ^n+n3^{n-1}+\frac{n(n-1)}{2}3^{n-2}+...+\frac{n(n-1)}{2}3^{2}+n*3+1-3n-1=\\3 ^n+n3^{n-1}+\frac{n(n-1)}{2}3^{n-2}+...+\frac{n(n-1)}{2}3^{2}$$by factoring 9$$ 3 ^n+n3^{n-1}+\frac{n(n-1)}{2}3^{n-2}+...+\frac{n(n-1)}{2}3^{2}=3^2(3 ^{n-2}+n3^{n-3}+\frac{n(n-1)}{2}3^{n-4}+...+\frac{n(n-1)}{2})=\\9k$$ so $$X=\left \{0,9,54,1008,.. \right \},Y=\left \{ 0,9,18,27,36,45,54,63,...\right \}$$ hence X is subset of Y ,because Y contain all of $9k$ , but X contain some of $9k$