Alright, it's with trepidation that I ask this, because dear god do I feel stupid. A question asked:
Whenever we run this formula we double x, then subtract 3 from the result. x = 5. What's the result if we do this 4 times? What's the result if we do it 12 times?5*2 = 10, 10 - 3 = 7. 7*2 = 14, 14-3 = 11 and so on.
At first I thought it would be simple: ((x*2)-3)*12; but that really doesn't come close to the correct value. Then I thought "aha, exponentiation!" but that's clearly not correct either.
Truth be told, I've never felt so bad at math as I do right now. Right now I just wonder: how would you write that? Where can I learn more on this? It's obvious that I'm going to need to refresh my math skills (and I want to learn more, because math is cool but it's been a while since I did any).
Additionally I feel a bit ashamed asking such a simple question here, because judging by the "similar questions" list I'm the village idiot. The village itself seem to consist of people who are amazingly good at math, so yeah -- it sucks to have to admit to being lost at something like this.
In fact, I'm so lost I don't even know what tags I should use.
Edit: I know the answer (I wrote a short for loop), I just want to know how I'd approach it mathematically instead.
$\endgroup$ 22 Answers
$\begingroup$For the particular function you have, we can figure out $f^{(n)}(x)$.
$f^{(1)}(x)=2x-3$
$f^{(2)}(x)=2(2x-3)-3=2^2x-(2+1)3$
$f^{(3)}(x)=2(2^2x-(2+1)3)-3 = 2^3x-(4+2+1)3$
$f^{(4)}(x)=2(2^3x-(4+2+1)3)-3 = 2^4x - (8+4+2+1)3$
The pattern is $f^{(n)}(x)=2^nx-(2^n-1)3$, which can be rearranged as $2^n(x-3)+3$. To prove this I would use induction.
$\endgroup$ $\begingroup$You’re starting with the function $f(x)=2x-3$. I’ll write $f^n(x)$ for the result of applying $f$ repeatedly $n$ times. Thus, you’re looking for $f^{12}(5)$ and more generally $f^n(x)$.
One elementary approach is to calculate $f^n(x)$ for some small values of $n$ and look for a pattern:
$$\begin{align*} f(x)&=2x-3\\ f^2(x)&=2f(x)-3\\ &=2(2x-3)-3\\ &=2^2x-2\cdot3-3\\ f^3(x)&=2f^2(x)-3\\ &=2\left(2^2x-2\cdot3-3\right)-3\\ &=2^3x-2^2\cdot3-2\cdot3-3\\ f^4(x)&=2f^3(x)-3\\ &=2\left(2^3x-2^2\cdot3-2\cdot3-3\right)-3\\ &=2^4x-2^3\cdot3-2^2\cdot3-2\cdot3-3\;. \end{align*}$$
At this point you can pick up a clear pattern:
$$f^n(x)=2^nx-2^{n-1}\cdot3-2^{n-2}\cdot3-\ldots-2\cdot3-3=2^nx-3\sum_{k=0}^{n-1}2^k\;.$$
If you know about geometric progressions (or just have some experience working with binary numbers) you can work out that
$$\sum_{k=0}^{n-1}2^k=1+2+2^2+\ldots+2^{n-2}+2^{n-1}=2^n-1\;,$$
so it appears that
$$f^n(x)=2^nx-3\left(2^n-1\right)=2^n(x-3)+3\;.\tag{1}$$
You can now check this: it certainly works when $n=1$, since it says that $$f(x)=2(x-3)+3=2x-3\;.$$ And if it’s right for $f^n(x)$, then it’s right for $f^{n+1}(x)$:
$$\begin{align*} f^{n+1}(x)&=f\big(f^n(x)\big)\\ &=2f^n(x)-3\\ &=2\Big(2^n(x-3)+3\Big)-3\\ &=2^{n+1}(x-3)+2\cdot3-3\\ &=2^{n+1}(x-3)+3\;, \end{align*}$$
exactly as $(1)$ would have it. (If you’re familiar with proof by induction, you’ll recognize this argument as an example.)
In particular, we can now compute $f^{12}(5)=2^{12}(5-3)+3=4096\cdot2+3=8195$.
$\endgroup$
