find all function such that $f:N->N$ for every $ n\in\mathbb{N} $, $f(f(n))+f(n)=2n$ PLZ->(solution not to use characterastic equation)<-
Problem
Source:
Tags: function, induction, strong induction, algebra unsolved, algebra
15.09.2014 03:12
I assume $N = \mathbb{Z}^+$ is the set of positive integers. Let $P(n)$ be the statement $f(f(n)) + f(n) = 2n$. We prove by strong induction that $f(n) = n$. For $n=1$, $P(1)$ immediately gives $f(f(1)) + f(1) = 2$. Since $f(f(1)) \ge 1, f(1) \ge 1$, and we achieve the minimum, we must have $f(1) = 1, f(f(1)) = 1$, thus proving the base case. Suppose that $f(n) = n$ for all $n < k$. For $n=k$, observe $P(k) \implies f(f(k)) + f(k) = 2k$. If $f(k) < k$, then $f(f(k)) = f(k)$ by induction claim, and so $f(f(k)) + f(k) = 2f(k) < 2k$, contradiction. If $f(k) > k$, then $f(f(k)) = 2k-f(k) < k$, and so observe $P(f(k)) \implies f(f(f(k))) + f(f(k)) = 2f(k)$. Since $f(f(k)) < k$, we have $f(f(f(k))) = f(f(k)) < k$ by induction claim, so the left hand side is less than $2k$. But $f(k) > k$, so the right hand side is greater than $2k$, contradiction. Thus $f(k) = k$. Thus $f(n) = n$ for all $n$ by induction.
10.05.2021 22:37
A sequence of natural numbers $(a_n)$ satisfies $a_{a_n}+a_n=2n$ for all $n\in\mathbb N$. Prove that $a_n=n$.
10.05.2021 22:46
We claim that $\boxed{f(n)=n}$ works (obvious) and is moreover the only solution. Strong induction follows: Base case. $n=1\Rightarrow f(f(1))+f(1)=2$, and since $f(n)\ge1$ we must have $f(1)=1$. Induction step. Assume that $f(k)=k\forall k<n$. We easily get that $f$ is injective. Combined with the strong induction claim, we must have $f(n)\ge n$. If $f(f(n))<n$, then $\exists m<n:f(m)=f(f(n))$, so $f(n)=m<n$ (injectivity), a contradiction. Thus $f(f(n))\ge n$ and $f(n)\ge n$, then the assertion gives $f(f(n))=f(n)=n$, completing the induction.
11.05.2021 09:22
Solution from my owen problembook: Quote: 1. Megoldás Mivel \[2x-f\left( x \right)=f\left( f\left( x \right) \right)>0\]ezért $f(x)<2x$ (1). Ezt ismételten alkalmazva kapjuk, hogy $2x=f(f(x))+f(x)<2f(x)+f(x)=3f(x)$ (2). Most az (1) és (2) összefüggések alapján felírható, hogy $\frac{2}{3}x<f(x)<2x$ (3). Ennek alapján az az ötletünk támadhat, hogy olyan ${{\left( {{a}_{n}} \right)}_{n\ge 1}},{{\left( {{b}_{n}} \right)}_{n\ge 1}}$sorozatokat keressünk, amelyekre ${{a}_{n}}x<f(x)<{{b}_{n}}x,\text{ }\forall \text{x}\in {{\mathbb{R}}_{+}},n\in {{\mathbb{N}}^{*}}$ (4). Ennek alapján azonban ${{a}_{n}}f(x)+f(x)<2x<{{b}_{n}}f(x)+f(x)$ ahonnan azt kapjuk, hogy $\frac{2}{{{b}_{n}}+1}x<f(x)<\frac{2}{{{a}_{n}}+1}x$ (*). Tehát értelmezhetők a következő sorozatok: ${{a}_{n+1}}=\frac{2}{{{b}_{n}}+1}$ és ${{b}_{n+1}}=\frac{2}{{{a}_{n}}+1}$ valamint ${{a}_{1}}=\frac{2}{3},{{b}_{1}}=2$. Könnyen belátható, hogy a két sorozat monoton, korlátos, ezért konvergens, és legyen $a=\underset{n\to \infty }{\mathop{\lim }}\,{{a}_{n}},b=\underset{n\to \infty }{\mathop{\lim }}\,{{b}_{n}}$ és ekkor a rekurziók alapján azt kapjuk, hogy $a=\frac{2}{b+1},b=\frac{2}{a+1}$ amit megoldva azt kapjuk, hogy ${{a}^{2}}+a-2=0,{{b}^{2}}+b-2=0$ amelyeknek a pozitív gyökei $a=b=1$ ezért a (*) összefüggésben ha határértékre térünk, akkor azt kapjuk, hogy $\frac{2}{b+1}x\le f(x)\le \frac{2}{a+1}x$$\Leftrightarrow \frac{2}{1+1}x\le f(x)\le \frac{2}{1+1}x$vagyis $f(x)=x$ és ezzel a feladatot megoldottuk. 2. Megoldás Indukcióval igazolható, hogy $f^{(n)}(x)=2x-f(x)+2^n (f(x)-x)$minden $n \geq 0$egész számra. Ha $f(x)-x<0$ lenne, akkor elég nagy $n$ esetén az előző egyenlet jobboldala negatív lenne, de a baloldala pozitív tehát muszáj $f(x) \geq x$De ekkor $2x=f(f(x))+f(x)\geq 2f(x)$, tehát $x\geq f(x)$. Végül tehát $f(x)=x$ $\forall x>0$.
11.05.2021 10:09
Basically strong induction and injectivity solves it. We start by noticing that f is injective. We play with small values like 1,2 and then notice that there is something that forces it to be n and then we use strong induction.
24.07.2022 06:27
jasperE3 wrote: A sequence of natural numbers $(a_n)$ satisfies $a_{a_n}+a_n=2n$ for all $n\in\mathbb N$. Prove that $a_n=n$.
07.10.2023 10:03
Can you check my solution i dont know it is correct or not 1. $f(1)=1$ subustitute n with $1$ gives us $ff(1)+f(1)=1$ If $f(1)<1$ or $f(1)>1$ then contradiciton. So $f(1)=1$ Lets assume $f$ is decreasing or equal function. Then $f(n+1) \le f(n) $ So we deduce that $f(n+1) \le f(n) \le ...... \le f(1)$ $f(1)=....=f(n+1)=1$ Then $2=2n+2$ contradiciton. Assume $f$ is increasing or equal function Then $\exists d, d+1:f(d)=f(d+1)$ $f(d) +ff(d) =f(d+1)+ff(d+1)=2d=2d+2$ contradiciton. Finally $f$ is increasing function. 1.Assume $f(n) >n$ So $ff(n) >f(n)$ $2f(n)<2n$ contradiciton. 2.Assume $f(n) <n$ Sk $ff(n) <f(n) $ $2f(n)>2n$ contradiciton again. So $f(n) =n$