How to proof that a function approaches infinity

May 2010
2
0
Let\(\displaystyle f: N -> N, f(n) = n + f(10n)\). How do i prove that f(1) approaches infinity?

I was thinking something like showing that there's no natural number p for f(1) < p, but i have no idea how to do this in practise. All help is appreciated :)
 

Plato

MHF Helper
Aug 2006
22,458
8,632
Let\(\displaystyle f: N -> N, f(n) = n + f(10n)\). How do i prove that f(1) approaches infinity?
Please check the statement that you posted. It makes no sense.
If \(\displaystyle f:\mathbb{N} \to \mathbb{N}\) then \(\displaystyle f(1) \in \mathbb{N}\) as such \(\displaystyle f(1)\) is a number.
Therefore it ‘approaches’ nothing but itself.
 
May 2010
2
0
Please check the statement that you posted. It makes no sense.
If \(\displaystyle f:\mathbb{N} \to \mathbb{N}\) then \(\displaystyle f(1) \in \mathbb{N}\) as such \(\displaystyle f(1)\) is a number.
Therefore it ‘approaches’ nothing but itself.
How come f: N -> N, f(n) = n + f(10n) makes no sense? f(1) = 1 + f(10) = 1 + 10 + f(100) = ... and so on. That's a recursive function.

Ah, now i got what you were saying. So should it be something like f: N -> inf? I don't know if infinity is an acceptable codomain.
 

Plato

MHF Helper
Aug 2006
22,458
8,632
Ah, now i got what you were saying. So should it be something like f: N -> inf? I don't know if infinity is an acceptable codomain.
That is correct. \(\displaystyle f(1)\) is a number.
Numbers are finite in \(\displaystyle \mathbb{N}\).
 
Jan 2010
354
173
We can only say some limit approaches infinity. Not an individual point in the function. By definition, it must have a single finite value assigned to it at each point in its domain.

Basically, the problem with the function you gave is that can't possibly be a function. No such function exists that satisfies that recursion.
 

HallsofIvy

MHF Helper
Apr 2005
20,249
7,909
It was not the "f(n) = n + f(10n)" that makes no sense, it was "f(1) approaches infinity". You want to show that f(n) approaches infinity as n goes to infinity. And, so, you do not want to show that there is no number p such that f(1)< p, you want to show that there is no number p such that f(n)< p for all.

Given any integer, p, look at f(p)= p+ f(10p). As long as you can show that f(n) is always positive, that is larger than p.

But even that would NOT be enough to show that f(n) goes to infinity- you would also have to show that f(n) is "eventually increasing"- that is, that for some N, if n> N, then f(n+1)> f(n).
 
Jan 2010
354
173
Edit: Nevermind, we're in the naturals. Ignore this post. :)
 
Last edited: