sets

May 2010
143
15
chennai,tamil nadu
if x={8^n - 7n - 1} and y={49(n-1)} prove that x is a subset of y
 

undefined

MHF Hall of Honor
Mar 2010
2,340
821
Chicago
if x={8^n - 7n - 1} and y={49(n-1)} prove that x is a subset of y
So presumably n is a positive integer.

You need to show that \(\displaystyle 8^n - 7n - 1 \equiv 0\ (\text{mod }49)\)

(The expression also must be non-negative but this is trivial.)

Use mathematical induction. Base case, n = 1.

\(\displaystyle 8^1 - 7(1) - 1 = 0 \equiv 0\ (\text{mod }49)\)

Induction step.

\(\displaystyle 8^{n+1} - 7(n+1) - 1 \equiv 8 \cdot 8^n - 7n - 7 - 1 \equiv (8)(7n+1) - 7n - 8 \equiv\)
\(\displaystyle 56n + 8 - 7n - 8 \equiv 49n \equiv 0\ (\text{mod }49)\)
 

Soroban

MHF Hall of Honor
May 2006
12,028
6,341
Lexington, MA (USA)
Hello, grgrsanjay!

If \(\displaystyle x\:=\:8^n - 7n - 1\,\text{ and }\,y\:=\:49(n-1)\), prove that: .\(\displaystyle x \subset y.\)

We want to show that \(\displaystyle x \:=\:8^n - 7n - 1 \) is always a multiple of 49.


We have: .\(\displaystyle x\;=\;8^n - 7n - 1\)

. . . . . . . . . \(\displaystyle =\;(7+1)^n - 7n - 1\)

. . . . . . . . . \(\displaystyle =\;\bigg[7^n + {n\choose n-1}7^{n-1} + {n\choose n-2}7^{n-2} + \hdots + {n\choose2}7^2 + {n\choose1}7 + 1
\bigg] - 7n - 1\)

. . . . . . . . . \(\displaystyle =\;7^n + {n\choose n-1}7^{n-1} + {n\choose n-2}7^{n-2} + \hdots + {n\choose2}7^2 \)

. . . . . . . . . \(\displaystyle =\;7^2\underbrace{\bigg[7^{n-2} + {n\choose n-1}7^{n-3} + {n\choose n-2}7^{n-4} + \hdots + {n\choose2}\bigg]}_{\text{This is an integer}} \)


Therefore: .\(\displaystyle x\) is a multiple of 49.