Question

تمام توابع $f:\mathbb N\to \mathbb N$ را بیابید به طوری‌که:

$$f(f(n))+f(n)=2n\qquad(\forall n \in \mathbb N)$$

متاسفانه نتوانستم راهی برای بدست آوردن جواب ارائه بدهم.

Answer 1

واضح است که $f(n)=n$ در این معادله تابعی صدق می کند. ثابت می کنیم جواب دیگری ندارد.

برای $n=1$ داریم $$f(f(1))+f(1)=2$$ از طرفی $f(n)\in \mathbb N$ و این تنها در صورتی امکان دارد که $f(1)=1$.

حال فرض کنید برای هر $n< k$ داشته باشیم $f(n)=n$ نشان می دهیم که $f(k)=k$.

قبل از این باید ذکر کنیم که تابعی که در فرض داده شده صدق کند یک به یک است(چرا؟)

دو حالت داریم یا $f(k)< k$ یا $f(k)>k$.

اگر $f(k)< k$ در اینصورت بنابر فرض استقرا داریم $f(f(k))=f(k)$ و از یک به یکی نتیجه می شود که $f(k)=k$ که مخالف فرض $f(k)< k$ است.

اگر $f(k)> k$ ادعا می کنیم $f(f(k))\geq k$ ؛ چون در غیر اینصورت داریم $f(f(k))< k$ و لذا بنابر فرض استقرا داریم $f(f(f(k)))=f(f(k))$ که از یک به یکی نتیجه می شود $f(f(k))=f(k)$ و باز از یک به یکی داریم $f(k)=k$ که مخالف فرض $f(k)> k$ است. در اینصورت $f(f(k))+f(k)\geq k+f(k)> 2k$ که فرض اصلی مساله را نقض می کند(چون بنابر فرض مساله $f(f(k))+f(k)=2k$).

پس تنها باید $f(k)=k$.

Comments

ببخشید این نوع استقرا که استفاده کرده اید، همان استقرا ضعیف است؟ چون من استقرایی که دیدم اینگونه بود که برای k فرض می شد که درست است و سپس برای k+1 اثبات می شد.

---

@Elyas1
خیر. استقرای قوی است. در استقرای ضعیف از درستی $P(n)$ درستی $P(n+1)$ را نتیجه می گیریم. در استقرای قوی از درستی $P(1), P(2), ..., P(n)$ درستی $P(n+1)$ را نتیجه می گیریم. و می توان نشان داد که با استقرای ضعیف معادل است.