I have a recursive formula: $f(n) = \frac{f(n-1)+1}{2} $ where $f(0) = h$
I should prove inductively that for any real h, f(n) will always eventually cross a threshold 1, meaning that f(n) will always eventually come to a value beneath 1 for any starting height h.
Generally, I can do induction but in this problem, I am having trouble because I am having trouble coming up with a base case and have no idea how to move on.
Computing the first few values of $f(n)$ by hand for arbitrary $h$ we see
$$f(0) = h,$$
$$f(1) = \frac{h}{2} + \frac{1}{2},$$
$$f(2) = \frac{h}{4} + \frac{1}{4}+ \frac{1}{2},$$
$$f(3) = \frac{h}{8} + \frac{1}{8}+ \frac{1}{4} + \frac{1}{2}.$$
Already I am led to make a conjecture for a closed form for $f(n)$. Can you conjecture what it might be before reading what I came up with? I conjecture
$$f(n) = \frac{h}{2^n} + \frac{1}{2^n}+ \frac{1}{2^{n-1}}+ \dots + \frac{1}{2}.$$
Sorry, I don’t know how to do the thing where I hide part of my answer unless you scroll over it. I should learn that. Anyways, you should try to prove that closed form for all $n$, maybe also by induction. When you have a lot of experience, a proof here isn’t necessary as it’s clear the closed form is accurate, but at your level it is good practice. Now, once you have that, we can simplify the closed form by using the finite geometric series formula. If you aren’t familiar with that, you can also look that up. It has an easy derivation that an advanced pre-calc student could understand.
Using the formula I mentioned, we simplify to
$$f(n) = \frac{h}{2^n} + \frac{(\frac{1}{2})(1-(\frac{1}{2})^{n})}{\frac{1}{2}},$$
so
$$f(n) = \frac{h}{2^n} + 1 - \frac{1}{2^n}, $$
and finally,
$$f(n) = \frac{h-1}{2^n} + 1.$$
Maybe now you might want to try on your own again to analyze this, and also question if what you are trying to prove is true. I see three cases:
If $h > 1$, $f(n)$ will converge monotonically down to 1, meaning it will never cross below 1.
If $h=1$, $f(n)$ is constant 1.
If $h < 1$, $f(n)$ will converge monotonically up to 1, meaning it is always less than 1.