Imagine a system where you go 40% of the way from 0 to 1 on a number line. Then imagine you go another 40%, but of the remaining distance instead of the original piece. Recurse. Define a model recurrence relation: $$f(0)=0.4$$ $$f(1)=0.4+0.4(1-0.4)$$ $$f(2)=0.4+0.4(1-0.4)+0.4(1-(0.4+0.4(1-0.4)))$$ $$f(3)=0.4+0.4(1-0.4)+0.4(1-(0.4+0.4(1-0.4)))+0.4(1-(0.4+0.4(1-0.4)+0.4(1-(0.4+0.4(1-0.4)))))$$ $$...$$ $$f(n)=\text{(see attempt below, not sure if right)}$$ $$...$$ $$f(\infty)=1$$
I tried to create a nice generalized recurrence relation, never mind solving it, but am not sure if it was right to plug into W|A/Mathematica to do RSolve, which I fiddled around with a bit. My best attempt is something like $f(n+1) = 0.4 + \sum_0^k 0.4(1-f(n))$.
(Edit 2: William made me realize my mistake. I didn't include adding the original $f(n)$ to the sum which I should've. This is because my original formula solved for just the $n+1$th term when I had set my function $f$ up differently (and I think it's still wrong anyway for that, but it's closer). So the correct form would be what William said: $f(n+1)=f(n)+0.4(1-f(n))$. This would be the first step of going from recurrence relation -> explicit formula. Now I just need to figure out how to do that...)
The way I solved it was by brute force and sheer coincidence I think, but I'm wondering if there's a better/more general way. Specifically, if I can make 0.4 any constant $c$ that'd be amazing. (I ended up doing this in my way, but I mean from the aforementioned general way.) Maybe I should try this: https://brilliant.org/wiki/recurrence-relations-method-of-summation-factors/?
Anyway, here goes my attempt.
First, let's expand each $f(3)$ and collect like terms. The first time I did this I did it by hand... big mistake. $$f(3)=4(0.4) - 6(0.4)^2 + 4(0.4)^3 - 1(0.4)^4$$ This (or at $f(2)$, don't quite remember) is where I realized what was happening. I immediately recognized Pascal's triangle, but with the first term cleaved off. This was the case for all $f$. Specifically, we're looking at a binomial theorem statement $(a+b)^n$. I quickly realized that $f(n)$ could be written in some form like $f(n)=(a+b)^n-a^n$. The alternating sign, however, was the thing that made it a bit different. Since even powers were negated, I figured to negate the entire thing but with negated odd power coefficients instead. Namely, $a=-1$ and $b=0.4$ (this order is imperative the way I define the formula). If I use $f(n)=(a+b)^n-a^n$, I'd get $f(n)=a^4+4a^3 b+6a^2 b^2+4a b^3+b^4-a^4=-4(0.4)+6(0.4)^2-4(0.4)^3+1(0.4)^4$, so again I just need to negate it, so $f(n)=-(a+b)^n+a^4$ where $a=-1, b=0.4$. Well, nicely enough, $-(-1+0.4)^n-(-1)^4=-(0.6)^n+1=1-(1-0.4)^n$. If I want to instead get my total remaining distance on the line, I just employ $1$ minus that, or $(1-0.4)^n$. For a general constant $c$, my formulae would be $1-(1-c)^n$ and $(1-c)^n$, respectively.
Now, this is where I can't figure out much more. My math education includes Calc 1-3 and Linear Algebra. Not having studied discrete mathematics, which is the subject that deals with recurrence relations, I didn't know how to go further. I tried looking at places like that brilliant link that generalize these type of recurrence relations with sums, but that presupposes that my summation equation way up top is right, and it just seems kind of random to pick one generalized formula over another. I was hoping someone knows of a way where I can get an explicit formula for $f(n)$ (from the beginning, involving a summation) and then go from that to an explicit formula with no summation, aka the answer I found of $f(n)=1-(1-c)^n$. While I did figure it out explicitly, I did it through brute force and the coincidence that I recognized the binomial theorem.
So, that is why I was wondering: is there a more intuitive way to see why the hell the binomial theorem shows up here. If not, how would one go from the set of equations to an explicit summation formula to an explicit formula (without summation)? (There's a possibility maybe one could skip this intermediate step, but I think it'd be a nice bridge if nothing else.)
Edit: I realize that you can invert the premise of the original problem, and realize that if you're going 40% of the remaining distance each time, this can be thought of in a different way. Start at 1 instead of 0 on the line and realize the distance from your progress (from 0) to 1, let's call it $d$, at each step of the summation you add 60% of $d$, so you'd do 60% $n$ times (or $d=0.6^n$), which is equivalent to $(1-0.4)^n$. Now to get the original distance from 0 to $d$, you'd do $1$ minus that, or the original answer $1-(1-0.4)^n$. However, I declare intuition like this to be cheating since it defeats my purpose of wanting to go from the other way this way. :)
Edit 3: Using William's general term formula and Wikipedia (https://en.wikipedia.org/wiki/Recurrence_relation#Solving_homogeneous_linear_recurrence_relations_with_constant_coefficients), I think I managed to do it. However, the (intuitive) link with the binomial theorem still remains a mystery to me. I start with William's $f(n+1)=f(n)+0.4(1-f(n))$, but with an index modification and generalizing $0.4$ to $c$. So, $f(n)=f(n-1)+c(1-f(n-1))=f(n-1)+c-c*f(n-1)=(1-c)f(n-1)+c$. Since this isn't homogenous, we can make it homogenous by $f: n \mapsto n+1$. So, $f(n+1)=(1-c)f(n)+c$. Accordingly, $f(n+1)-f(n)=(1-c)f(n)+c-((1-c)f(n-1)+c)=(1-c)f(n)+c-(1-c)f(n-1)-c=(1-c)f(n)-(1-c)f(n-1) \Rightarrow f(n+1)=(1-c)f(n)+f(n)-(1-c)f(n-1) \Rightarrow f(n+1)=(2-c)f(n)-(1-c)f(n-1)$. This is now homogenous.
Now, the characteristic equation for $f$ would be $p(t)=t^2-(2-c)t+(1-c)$. This factors to $(t-1)(t-(1-c))$. This gives us roots $r_1=1, r_2=(1-c)$. Now, $f(n)=k_1r_1^n+k_2r_2^n$. Since $f(0)=0$ and $f(1)=(1-c)f(0)+c=(1-c)(0)+c=c$ (see equation above), then $(1): f(0)=0=k_11^0+k_2(1-c)^0=k_1+k_2$ and $(2): f(1)=c=k_11^1+k_2(1-c)^1=k_1+(1-c)k_2 \Rightarrow k_1=c-(1-c)k_2$. Now substitute $(2)$ into $(1) \Rightarrow 0=c-(1-c)k_2+k_2 \Rightarrow -c=k_2(1-(1-c)) \Rightarrow k_2=-\frac{c}{1-(1-c)}=-\frac{c}{c}=-1$. Substitute $k_2=-1$ into $(1)$ now $\Rightarrow 0=k_1+k_2\Rightarrow 0=k_1-1\Rightarrow k_1=1$. So, $f(n)=k_1r_1^n+k_2r_2^n=(1)(1)^n+(-1)(1-c)^n=1-(1-c)^n. \text{QED}.$
Now just need to figure out why the binomial theorem is in here. Not algebraically like with the expansion of $(a+b)^n$, but intuitively from the original problem's context.