با برهان خلف ثابت کنید که هر دو جملهٔ متوالی دنبالهٔ فیبوناچی نسبت به هم اول هستند

Question

با سلام خدمت تمام کاربران و اساتید سایت محفل ریاضی ایرانیان

می‌دانیم که دنبالهٔ فیبوناچی، دنباله‌ای است به‌صورت زیر:

$$\{1,1,2,3,5,8,13,21,34,55,...\}$$

که در آن هر جمله (به‌جز جملهٔ اول و دوم) برابر با حاصل جمع دو جملهٔ قبلی است.

و شاید بدانید که:

هر دو جملهٔ متوالی دنبالهٔ فیبوناچی نسبت به هم اول هستند.

این موضوع درست است اما آن را چگونه می‌توان با برهان خلف اثبات کرد؟

تلاش انجام‌شده:

اول فرض کردم که حکم نادرست باشد، پس فرض می‌کنیم که در دنبالهٔ فیبوناچی داریم:

$$F_n=m\cdot p$$

$$F_{n+1}=k\cdot p$$

این یعنی این که دو جملهٔ متوالی در دنباله وجود دارند که نسبت به هم اول نیستند و عامل مشترک ($p$) دارند.

در نتیجه:

$$F_{n+1}=F_{n}+F_{n-1} \Longrightarrow F_{n-1}=F_{n+1}-F_n \Longrightarrow F_{n-1}=kp-mp=(k-m)\cdot p$$

پس $F_{n-1}$ هم بر $p$ بخش‌پذیر است. به همین شکل می‌توانیم نتیجه بگیریم که $F_{n-2}$ و $F_{n-3}$ و $F_{n-4}$ و... همگی بر $p$ بخش‌پذیر هستند و آنقدر به عقب می‌رویم تا به جملهٔ دوم دنباله می‌رسیم و نتیجه می‌گیریم که جملهٔ دوم دنباله هم بر $p$ بخش‌پذیر است. اما این یک تناقض است؛ زیرا جملهٔ دوم دنباله برابر با عدد یک است و $p>1$ و عدد یک فقط بر خودش بخش‌پذیر است. اما ما نتیجه گرفتیم که عدد یک بر $p$ که بزرگتر از یک است بخش‌پذیر است! پس به تناقض رسیدیم و فرض خلف باطل شد و در نتیجه درستی حکم اثبات شد.

Comments

خب اثبات شما درسته دیگه

Answer 1

می‌توانیم مستقیماً از استقرای ریاضی استفاده کنیم. واضح است که دو جملۀ اول دنباله، نسبت به هم اولند. فرض می‌کنیم: $$(F_k, F_{k+1})=1 $$ حال نشان می‌دهیم که دو جملۀ متوالی بعدی هم نسبت به هم اولند: $$(F_{k+1}, F_{k+2 }) =(F_{k+1},F_{k+1}+F_k)=(F_{k+1},F_k) =1 $$

Answer 2

فرض کنید دو جملهٔ متوالی دنبالهٔ فیبوناچی را با اعداد $n$ و $n+1$ نشان دهیم. بنابراین، جملهٔ قبلی این دو جمله با شمارهٔ $n-1$ برابر است با:

$F(n-1) = F(n) - F(n-2)$

جایگذاری مقدار فیبوناچی متناظر با هر جمله در این رابطه، به شکل زیر خواهد بود:

$F(n-1) = F(n) - F(n-2)$

$F(n-1) = (F(n-1) + F(n-2)) - F(n-2)$

$F(n-1) = F(n-1)$

بنابراین، دو جملهٔ متوالی دنبالهٔ فیبوناچی همواره نسبت به هم اول هستند.

Answer 3

فرض کنید دو جملهٔ متوالی از دنبالهٔ فیبوناچی را با نام‌گذاری $F_n$ و $F_{n+1}$ در نظر بگیریم. برای ثابت کردن اینکه این دو جمله نسبت به هم اول هستند، باید نشان دهیم که تنها یک مقسوم عمومی بین آن‌ها وجود دارد و آن هم ۱ است.

برای این منظور، فرض کنید $d$ مقسوم عمومی $F_n$ و $F_{n+1}$ باشد. بنابراین داریم:

$$d | F_n \quad \text{و} \quad d | F_{n+1}$$

با توجه به تعریف دنبالهٔ فیبوناچی، داریم:

$$F_{n+1} = F_n + F_{n-1}$$

بنابراین:

$$d | F_{n+1} - F_n = F_{n-1}$$

حال باید نشان دهیم که $d$ باید برابر با ۱ باشد. اگر فرض کنیم $d$ برابر با ۲ باشد، داریم:

$$2 | F_n \quad \text{و} \quad 2 | F_{n+1}$$

با توجه به تعریف دنبالهٔ فیبوناچی، هر جملهٔ زوج بعدی برابر با جمع دو جملهٔ فردی قبلی است. بنابراین، اگر $F_n$ زوج باشد، آنگاه $F_{n-1}$ فرد و $F_{n-2}$ زوج است. با توجه به اینکه $F_0 = 0$ و $F_1 = 1$ فرض می‌کنیم که $n \geq 2$، بنابراین داریم:

$$F_n = F_{n-1} + F_{n-2}$$

$$F_{n+1} = F_n + F_{n-1}$$

از این دو رابطه داریم:

$$F_n + F_{n+1} = 2F_{n-1} + F_n = F_n(2 + \phi)$$

که در آن $\phi$ نسبت به طرز تعریف دنبالهٔ فیبوناچی، نسبت به ۱ بیشتر است. بنابراین، اگر $F_n$ زوج باشد، باید $F_n(2 + \phi)$ نیز زوج باشد. با توجه به اینکه $\phi$ بیشتر از ۱ است، $2 + \phi$ نیز بیشتر از ۲ است و بنابراین $F_n$ باید مقسوم بر ۲ باشد که با فرض ما در تناقض است.

بنابراین، فقط یک مقسوم عمومی بین $F_n$ و $F_{n+1}$ وجود دارد که آن هم ۱ است و بنابراین این دو جمله نسبت به هم اول هستند.