how to solve a recurrence relation (3 ways + 1 bonus)
ฝัง
- เผยแพร่เมื่อ 1 ส.ค. 2024
- Here are 3 typical ways of solving a recurrence relation. These are usually taught in a discrete math class. Subscribe to @blackpenredpen for more fun math videos.
Timestamp:
1st way (either you love it, or you hate it): 0:22
2nd way (use a_n=r^n): 4:15
3rd way, use generating function/infinite series: 17:40
BONUS: 36:16
An explicit formula for the Fibonacci sequence (second order difference equation): • Nth term formula for t...
---------------------------------------------------------------------------------------------------
**Thanks to ALL my lovely patrons for supporting my channel and believing in what I do**
AP-IP Ben Delo Marcelo Silva Ehud Ezra 3blue1brown Joseph DeStefano
Mark Mann Philippe Zivan Sussholz AlkanKondo89 Adam Quentin Colley
Gary Tugan Stephen Stofka Alex Dodge Gary Huntress Alison Hansel
Delton Ding Klemens Christopher Ursich buda Vincent Poirier Toma Kolev
Tibees Bob Maxell A.B.C Cristian Navarro Jan Bormans Galios Theorist
Robert Sundling Stuart Wurtman Nick S William O'Corrigan Ron Jensen
Patapom Daniel Kahn Lea Denise James Steven Ridgway Jason Bucata
Mirko Schultz xeioex Jean-Manuel Izaret Jason Clement robert huff
Julian Moik Hiu Fung Lam Ronald Bryant Jan Řehák Robert Toltowicz
Angel Marchev, Jr. Antonio Luiz Brandao SquadriWilliam Laderer Natasha Caron Yevonnael Andrew Angel Marchev Sam Padilla ScienceBro Ryan Bingham
Papa Fassi Hoang Nguyen Arun Iyengar Michael Miller Sandun Panthangi
Skorj Olafsen Riley Faison Rolf Waefler Andrew Jack Ingham P Dwag Jason Kevin Davis Franco Tejero Klasseh Khornate Richard Payne Witek Mozga Brandon Smith Jan Lukas Kiermeyer Ralph Sato Kischel Nair
---------------------------------------------------------------------------------------------------
💪 If you would also like to support this channel and have your name in the video description, then you could become my patron here / blackpenredpen
Thank you
Pikachu was throwing shade.
His way doesn't always work.
How cancel I contact with you?
Pikaaaaa (with lightning strikes)
How can I differentiate and integrate
Riemann ζ function
pikachu method is how i usually do it, but i somehow never looked into analogy between discrete difference equations and continuous differential equations - definitely gonna try method 2 more in the future
please answer the question that i gave you in last video i want solution i have answer which is f(x)=alnx and the answer of f(1)=0
Son of blackpenredpen In a few years:
3 ways to solve te Riemann hypothesis.
Lol
I actually solved it but the comments section is too small for me to write the proof, so I'm leaving it as an exercise to the readers. It's easy anyways, super trivial stuff.
@@mrocto329 claim your $1M prize then
@@anon1963 I find managing money to be an inconvenience. I'd rather focus on my future proofs than be bothered by material gains. I've actually solved P-NP problem in the past 10 months, but I sadly used the paper I wrote the proof on to wipe my ass so I won't be able to share it anytime soon.
@@mrocto329 same here. I formulated the theory of everything and proved it but sadly my dog ate the papers.
Divide 2ⁿ on both sides
a_n/2ⁿ=a_n-1/2^(n-1) -1
Consider a_n/2ⁿ as a series b_n
b_n=b_n-1 -1
So b_n is an arimethric series where d=-1, b1=8/2=4
So
b_n=4+ (n-1)(-1)
a_n/2ⁿ=5-n
a_n=(5-n)2ⁿ
Wow this is neat!
intresting fun fact: th-cam.com/video/YIs3th01NV0/w-d-xo.html
Wait I think there should be a 2 after the equals sign in the first line
@@Robin-Dabank696 thanks for pointing out
Amazing
To understand recursion you need to understand recursion
LOLLLLL
You need to understand the principle of induction lol
intresting fun fact: th-cam.com/video/YIs3th01NV0/w-d-xo.html
I love how I can learn better from a man dressed as pikachu than I can a professor in a suit.
Probably bc you can actually stay awake with this guy
As I watched through the first 2 solutions, I kept thinking you wouldn’t mention generating functions, but what do you know, the best for last!
Thanks!!!
Summation factor is also an effective way of solving those equations. I learned about this in my algorithm class, where we had to find the big O notation of an recursive function
Amazing! You are a genius and look like you're having a blast teaching us. We need more teachers like you!
Actually, it is possible to solve the equation (y'' - 3y' + 2y)(t) = e^(2t) systematically and without needing to guess that y = e^(rt). In fact, the process of solving the homogenous equation first and modifying the solution to solve the inhomogeneous equation is not necessary either. Let the derivative operator be represented by D, such that y'(t) = Dy(t). Then y''(t) - 3y'(t) + 2y(t) = (D^2)y(t) - (3D)y(t) + 2y(t) = (D^2 - 3D + 2)y(t) = e^(2t). D^2 - 3D + 2 is a polynomial in D, and since D is a continuously linear operator, D^2 - 3D + 2 = (D - 2)(D - 1). Therefore, (D - 2)(D - 1)y(t) = e^(2t). Let z(t) = (D - 1)y(t). This gives us the linear system of equations (D - 2)z(t) = e^(2t) and (D - 1)y(t) = z(t). Solving the first equation is done by exploiting the product rule of differentiation, so it be solved systematically and without guessing, and once z(t) is known, solving the second equation is trivially the same process.
The same applies with recurrence equations, the only difference being that, instead of considering a polynomial on the operator D, you consider a polynomial on the operator e^D = S, the shift operator. This is, of course, unless the equation is nonlinear, in which it is more complicated than working with a polynomial.
Angel Mendez-Rivera thank you so much i was trying to come up with that myself because it seemed possible but i just couldn’t do it, you just solved half of the problems in my life dude
Yes! There's a ton of analogies between DEs and difference equations. A good book on that is Saber Elaydi's "An Introduction to Difference Equations".
Excuse me I'm not very familiar with D operator or I might've missed something... What is the 'exploiting the product rule' part?
Geometry Dash Mega If you have an equation of the form y'(t) + p(t)y(y) = q(t), you can multiply by a function r(t), resulting in r(t)y'(t) + r(t)p(t)y(t) = q(t)r(t). Now, think this to yourself: would it not be awesome if you had r(t)y'(t) + r'(t)y(t) on the left side of the equation? Yes, it would be, because then you can rewrite this as [r(t)y(t)]', or with the better notation, D[r(t)y(t)], denoting the derivative of a product. This is why I said you can exploit the product rule. From here, you simply have to integrate over the appropriate region, and then divide by r(t) to isolate y(t) and get your solution.
This establishes how to solve the equation r(t)y'(t) + r'(t)y(t) = q(t)r(t), but the equation you want to solve is r(t)y'(t) + p(t)r(t)y(t) = q(t)r(t). How do you go from the second to the first? By comparing coefficients, you realize that r'(t) = p(t)r(t), and now you can solve for r(t) very easily and find some expression for it. The way to do it is by dividing by r(t) to get r'(t)/r(t) = p(t). You should recognize that r'(t)/r(t) = D(ln[r(t)]), such that ln[r(t)] = Integral[p(t)]. Hence r(t) = e^Integral[p(t)]. With this, the problem reduces to solving D[r(t)y(t)] = q(t)r(t), where now both q(t) and r(t) are known. Then y(t) = Integral[q(t)r(t)]/r(t). This gives you the solutions that you want.
Okay, but you may be wondering, "why is solving y'(t) + p(t)y(t) = q(t) relevant to solving (D - 2)z(t) = e^(2t)?" It is relevant because (D - 2)z(t) = Dz(t) - 2z(t) = z'(t) - 2z(t) = e^(2t), and the equation now has the form z'(t) + p(t)z(t) = q(t), which I just told you how to solve by exploiting the product rule. This is true if you consider that p(t) = -2 and q(t) = e^(2t).
Once you have solved for z(t), you can solve the equation (D - 1)y(t) = z(t) with the same procedure.
intresting fun fact: th-cam.com/video/YIs3th01NV0/w-d-xo.html
Wow! So nice! You rock! I love the first method!!! I just realized that you made a video on recursion after searching for recursion on YT. Your video was recommended to me! 🤩
I shared the link to your video in my comment to my own video on a recursive sequence. 💖
My professor gave us a harder version of this on our final and it took me so long using generating functions but we had to use it! Realizing we needed the derivative to the longest time
A new field of study for me. Thank you.
Thank you soooo much I haven't been to lectures and you saved me! :D
真好，终于看到了微分方程和差分方程对比的vid，谢谢
Thanks for your videos man, you help me a lot. Thanks
It's almost 3 a.m in my country and at 8 I have online math test... I am lucky that I am very good at math and I love it because once I solve 1 tipe of exercise I can solve all I never take an 9 on math... I am in high school second year but I can solve even four year math problem I watch your videos because I love all tipe of math geometry trigonometry physics... I really like your videos are too interesting some times I dont know what are you talking about but I like it anyways because you say what are you doing soo I can a little understand go ahead and continue making video 👍👍😜😜😜👍👍👍
Thank you so much for this !!
I like your style and enthusiasm
The third solution was very nice.
Solving recurrence relations was probably the most fun aspect of solving differential equations when I took the course back in college.
This was so helpful! I was always looking for a video who explains three concise ways to get the direct equation!
Also I'm just wondering how you setup your camera in these videos.
great explanation! thank you
i love your pikachu way! You can also use Z-transformation in the control theory to solve this as well
Love this guy
You can simplify the equation by looking for a substitution. At first, I tried a_n = b_n - C*2^n, but nothing cancelled, so I tried a similar method to Differential equations and tried subtracting C*n*2^n. Everything cancelled nicely when c=1. Then you just had a geometric sequence left for b_n, and using the modified initial condition you got b_n=5*2^n. Therefore a_n= 5*2^n - n*2^n
Thanks for the video =)
You could also assume an equivalent second order linear homogenous recurrence relation a(n) = A*a(n-2) + B*a(n-1). Looking at the first few terms, you get A*5 + 8*B = 12, A*8 + 12*B = 16, giving you A = -4, B = 4 and a(n) = -4*a(n-2) + 4*a(n-1), a(0) = 5, a(1) = 8. You could verify the assumtion by checking the next few terms. Solving this in usual way, also gives you a(n) = (5-n)*2^n
You could obtain your second order linear homogenous recurrence relation in a simpler and more elegant way from the first order linear non homogenous recurrence relation:
(1) a_n = 2a_(n-1) - 2^n
(2) a_(n-1) = 2a_(n-2) - 2^(n-1)
By multiplying eq. (2) by -2 and adding to eq. (1) we obtain:
a_n - 2a_(n-1) = 2a_(n-1) - 4a_(n-2) or:
(3) a_n = 4 ( a_(n-1) - a_(n-2) ) for each n≥2, where: a_0=5, and a_1 = 2∙5 - 2 = 8.
Solving systematically eq. (3) you obtain indeed the solution: a_n = (5-n) 2^n. However, the question is why you consider a second order linear homogenous recurrence relation being simpler than a first order linear non homogenous one.
A very interesting presentation!
Regarding the second method is there any special reason for comparing the recurrence relation to a second order linear ODE instead of a first order one, i.e.: y'-αy=β^αt together with initial value: y(t_0 )=y_0 ?
I remember learning this through the holy book Boyce DiPrima Differential equations
Wow so interesting!
Nice. Video.. Sir u r really great teacher
recurrence equations are my favorite
This vid is awesome
I did one like the 4th,but I think it's more complicated.
1/(2^1)*a1=
1/(2^0)a0-2^(1-1)
1/(2^2)*a2=
1/(2^1)a1-2^(2-2)
1/(2^3)*a3=
1/(2^2)a2-2^(3-3)
.
.
.
1/(2^n)*an=
1/(2^(n-1))a(n-1)-2^(n-n)
then cancel them.
am i the only one who gets comedic value out of this as well? BPRP is hilarious
Can you link to Peyam and your videos that you referred to at 11 minutes?
just keep iterating, replace a_{n-1} with its recurrence relation and you see a pattern emerging. My favorite is Method 3, I came across it in a Combinatorics lecture by Frederico Ardilla. Though I must say, Method 2 was new to me, it was definitely a neat trick
Yup that’s what pikachu did at the end : )
I Like Pikachu and his method... :P
intresting fun fact: th-cam.com/video/YIs3th01NV0/w-d-xo.html
This video is amazing!!! Can you do a non linear recurrence relation next?
The Double Helix Someone in the comments suggested the following non-linear recurrence relation problem:
a(n + 1) = floor[1.3·a(n)] + 1.
intresting fun fact: th-cam.com/video/YIs3th01NV0/w-d-xo.html
Why we start indexing terms of series from zero while defining generating function ?
First term in the sequence a_{n} is indexed with zero
Why we start indexing terms of series from one while plugging series into recurrence relation ?
Recurrence relation is valid from n = 1
THANK YOU FOR THE AVATAR!!!!!!!!!
Incredible
Excellent! I miss the previous blackboard...
The generating function method is the best. I use the following (which is a generalization of the differentiation) Sum(n=c, infinity, b.a^(n-c).Comb(n-c+k, k).x^n) = b.x^c/((1-a.x)^(k+1)). Using that you get G(x) = (a0+1)/(1-2.x) + -1/(1-2.x)^2 then you convert and get an = (a0+1).2^n.Comb(n,0) + -1.2^n.Comb(n+1,1) which simplifies to an = (a0+1).2^n + -1.2^n.(n+1) = (a0+1-n-1).2^n = (a0-n).2^n. Simple and fast. Doing Fibonacci: a0=0, a1=1, an=an-1 + an-2. You get G(x) = (a0.1 + (a0+a1).x)/(1-x-x^2). Replace a0 and a1 and G(x) = x/(1-x-x^2). We need to find the form 1/(1-x) so C1/(1-d.x) + C2/(1-e.x) = x/(1-x-x^2) or (C1.(1-e.x) + C2.(1-d.x))/((1-d.x).(1-ex)) = x/(1-x-x^2). If the denominators are equal then the numerator will be equal also, so we solve (1-d.x)(1-e.x) = 1-x-x^2 and get either d=(1-sqrt(5))/2, e=(1+sqrt(5))/2 or d=(1+sqrt(5))/2, e=(1-sqrt(5))/2. Since d and e are interchangeable, pick the first. Now we solve C1.(1-e.x) + C2.(1-d.x) = x and we get C1= -1/(e-d), C2=1/(e-d), so G(x) = (e-d)^-1/(1-e.x) - (e-d)^-1/(1-d.x). Then we convert and get an = (e-d)^-1.e^n.Comb(n,0) - (e-d)^-1.d^n.Comb(n,0) which simplifies to an = (e^n-d^n)/(e-d).
@Dr.Peyam explained to solve the 2nd order differential without guessing!!!
Bprp: bruh
The beginning of my algorithms class involved solving recurrence relations. The Master Theorem could make a great video btw!
What’s the master theorem?
@@blackpenredpen If you're familiar with divide and conquer algorithms (like merge sort), the master theorem can place tight asymptotic bounds (Big Theta) on specific kinds of recurrence relations.
0:01 that sad mood I cried on.
Sir can you make video on inverse Laplace transform of 1/sqrt(s)
For an explicit form of the Fibonacci sequence, you can use Binet's Formula (i've just find it. It is pretty neat!)
Diego Mathemagician He knows that, he even said in the video that he made a video on the formula and deriving it three years ago. And it's true: I watched the video.
@@angelmendez-rivera351 he actually made a hidden video lol th-cam.com/video/UrROAw-Ngxs/w-d-xo.html
By the GODS, what fortuitous timing!
?
@@blackpenredpen lol my professor gave us assignment with solving linear homogeneous recurrence relations. Its taken some time but I appreciate any approach I find :)
Ah i see!! Best of luck!! Those are fun stuff!
@@blackpenredpen Well...the toy examples he's given us in class are pretty straightforward. I want to get a head start on the more difficult ones. Thanks again for the video!
I remember the time when I was a college student working for all those ugly patterns recurrence problems~ Memory flashing back haha
Similar to the third method is Z transformation
Summation factor also works for this equation
30:18 Believe me here it is better to start indexing from zero
and then multiply both sides of equation by x
Can you explain the Simplex algorithm in a video?
Power Series joke killed me
0:07 Dude, you gave me hope by solving those equations. Now, do u have an equation for me to solve that can help me get along with her family. 🤣
Tell math jokes. It works!
Hey, hey hey!! ,.. Please tell what to do in this..
a(n) =2/3a(n-1)+n^2-15. n and n-1 are subscripts
Can we solve this question by characteristics root method?
Please explain this type of question by characteristics root method.
Thanks 👍👍
This is not geometric...
This is not arithmetic...
THIS IS NOT NICE!
😂
This is an arithmetico-geometric progression
The method of "generating functions" has another name in system information engineering: _Z-Transformation_ ! If you have the appropriate transformation tables and practiced a little, this method will be actual _very_ fast, easy and foolproof!
Instead of guessing some solutions, you will calculate partial fraction decompositions, just like using the Laplace-Transform for LTI's (linear time-invariant systems). In fact, the Z--Transform does the same thing for recurrence relations as the Laplace-Transform for LTI's!
*Rem.:* Fun fact: All those "guessing rules" for solving LTI's and recurrence relations can be found by asking: "Which kind of terms can I get after partial fraction decomposition, depending on the coefficients of my LTI/recurrence relation?"
4th way is using matrices
You are blackpenredpenbluepen now
I looked at the tittle and expect that you would provide this method,
So I will write it down here
We have 2^n= 2a_(n-1) - a_n
And 2^n=2.2^(n-1)= 4a_(n-2) - 2a(n-1).
Substract these two equation. We have
0=a_n - 4a_(n-1) + 4a_(n-2) holds for any n>1
Now, by characteristic equation formula, we have that
a_n = (A+Bn)2^n.
Since a_0=5, then A=5. Since a_1=8, then B=-1
Therefore a_n=(5-n)2^n.
What about the cases that the recurrence relation isn't linear?
How can integrate (e^x/x)dx
10TH GRADER'S MIND:"KABOOOOOOM!!!!"
NICE VIDEO
I like the last one best. But I'm interested why it's not possible to solve Fibonacci with it? I get a_n = a_n+1
I have a solution which does not need particular solution
We know 2(2^(n-1)) =2^n
But 2^n = 2(an-1)-an
By substituting
We get (an+1)-4(an)-4(an-1)=0
Which gives an=2^n(an+b)
Now either by using the first two terms or using the first term and the orignal equation we get the solution
Oh nice. And I think that’s similar to what pikachu did at the end of the video.
At 30:21 shouldn't the derivative be
-1/(1-x)^2
Generating Function is similar to Z transform w/ x=z^-1, and Z transform may be easier to solve with...
great
are you from usa or singapore?
"Our favorite constant: c."
(Paraphrased for presentation)
xD
24:30 how do you know |X| < 1? I thought the infinite geometric series doesn't converge if this condition is not satisfied?
You do not care about it's convergence. X is arbitrary, and as such you can assume that the sum converges.
40min video at 9:51 am
very good ;)
Here is another solution:
Because there are two "2" in the recursive formula, we can consider the serie: Bn = An / 2^n
Applying the recursive formula gives:
B(n+1) = Bn - 1
Since B0 = 5, we have:
Bn = 5 - n
and finally
An = (5-n)*2^n
bruh
tnx alot.
last method.
Penalty Goal # Fantanstic
What happened to your video after this? I saw it, but did not have a chance to watch it, and now it is gone.
Pikachu is amazing!
But I gotta know, how did you get him in the video? :o
Jokes aside, pikachu way is definitely the coolest. I have a pikachu costume, myself!
I have a way of solving recurrence relations that is different but similar-ish that I learned for computing the complexity of computer algorithms. If I could get some contact info, id be happy to discuss it.
I used to work for tcc. You are in eastern Washington right? Scc was it?
@@seraphikimercury4921 oh ok
intresting fun fact: th-cam.com/video/YIs3th01NV0/w-d-xo.html
Sir, can you please suggest me book for special function for physics I am in final sems of Master of science in physics.
Here, sir you can mail me rs.rahulsinghtu@gmail.com
I will highly thankful of you
Can you solve this?
T(n) = T(n - 1) + cn, if n > 1
T(1) = 0
What if we want to find a formula for a(n) in terms of n given that a(n) = floor(1.3a(n-1) + 1) and a(0) = 3?
William Adams floor[1.3a(n - 1) + 1] = floor[1.3a(n - 1)] + 1, so this already can be helpful. However, this is nonlinear, so the last two methods employed in this video are not simply going to work. It may be easier to just list the first few terms and find another recognizable pattern that relates them, although there is no guarantee here either.
a(0) = 3
a(1) = floor[(1.3)(3)] + 1 = 4
a(2) = floor[(1.3)(4)] + 1 = 6
a(3) = floor[(1.3)(6)] + 1 = 8
a(4) = floor[(1.3)(8)] + 1 = 11
a(5) = floor[(1.3)(11)] + 1 = 15
At the very least, what this tells you is that this sequence is monotonically increasing.
I don't think it's possible to solve this equation explicitly, though. I tried BPRP's final secret method, and I obtained contradictory results.
a(n) = floor[1.3a(n - 1)] + 1 = floor[1.3·(floor[1.3a(n - 2)] + 1)] + 1= floor(1.3·floor[1.3·a(n - 2)] + 0.3) + 2 = floor(1.3·floor[1.3·(floor[1.3·a(n - 3)] + 1)] + 0.3) + 2 = floor[1.3·floor(1.3·floor[1.3·a(n - 3)] + 0.3) + 0.3] + 3. From here, you can use the schema of mathematical induction to prove that, if we define g(x) = floor(1.3x + 0.3), then a(n) = [g^(m - 1)](floor[1.3·a(n - m)]) + m, where m is in the interval [1, n]. Then let m = n, so a(n) = [g^(n - 1)](floor[1.3·a(0)])+ n = [g^(n - 1)](3) + n for n > 0, and since both [g^(n - 1)](3), and n are increasing sequences, it follows that a(n) is a monotonically increasing as well. Also, this reduces the problem of solving the recurrence equation into the debatably simpler problem of finding a explicit expression for [g^(n - 1)](3), where, as I said earlier, g(x) = floor(1.3x + 0.3)
Your best chance for finding a explicit expression for f(n) is once again to list numbers here.
(g^0)(3) = 3
(g^1)(3) = floor[(1.3)(3) + 0.3)] = floor(4.2) = 4
(g^2)(3) = floor[(1.3)(4) + 0.3] = floor(5.5) = 5
(g^3)(3) = floor[(1.3)(5) + 0.3] = floor(6.8) = 6
(g^4)(3) = floor[(1.3)(6) + 0.3] = floor(8.1) = 8
implying
a(1) = 3 + 1 = 4
a(2) = g(3) + 2 = 6
a(3) = (g^2)(3) + 3 = 8
a(4) = (g^3)(3) + 4 = 10
a(5) = (g^4)(3) + 5 = 13
These are clearly not the numbers given earlier. This must mean the method is invalid, or I made my calculations wrong, but I have checked the calculations over 5 times now and I have found no mistake. And I cannot see why the method would be inapplicable either.
Never mind what I said in my second comment. I calculated a(n) wrong because I used the distributive properties of the floor function incorrectly, because I forgot to use parentheses. I decided to do this on paper and by hand and I figured out the actual correct formula.
Consider the function (f[m])(x) = floor[1.3x + 0.3m], and let • denote functional composition. By this, a(n) = floor[1.3·a(n - 1) + 1] implies a(n + m) = (f[m - 1] • ... • f[0])[a(n)] + m. Letting n = 0 means a(m) = (f[m - 1] • ... • f[0])(3) + m, which implies that a(m) is monotonically increasing, which is precisely what I claimed before. Now the problem has been reduced to finding a explicit expression for (f[m - 1] • ... • f[0])(3) = g(m), which again, is really done best for now by listing. This time, the formula does match the previous numerical results, thus no contradiction arises. Finding an explicit expression for g(m) is even harder, though, possibly impossible anyway, as I mentioned earlier.
g(0) = 3
g(1) = floor(3.9) = 3
g(2) = floor(4.2) = 4
g(3) = floor(5.8) = 5
g(4) = floor(7.4) = 7
g(5) = floor(10.3) = 10
The new information that we gain from this numerical list is that g(n) = floor[h(n)], and that h(n) >> An + B. In other words, h(n) grows faster than any linear function.
I thought about it further, and I realized that a(n) must have super-polynomial growth, most likely exponential growth, to be exact. The reason I argue this must be the case is because if we look at the recurrence relation b(n + 1) = floor[1.3·b(n)], it becomes obvious why this has super-polynomial growth. Adding 1 at every iteration of the recurrence can only increase its growth, and this is what you are doing with a(n). This works because 1.3 > 1. So it may be appropriate to look for a solution of the form a(n) = floor[r^K(n)] or a(n) = p^floor[L(n)].
Another strategy you can attempt is by realizing that floor[Ax] = q(x)·floor(x) for some function q if A is not an integer.
Angel Mendez-Rivera Yeah I could write floor(1.3a(n-1)+1) as a(n - 1) + 1 + floor(0.3a(n - 1)), then I was stuck.😅
Imagine this as an Olympiad question but they ask you to figure out the general term given the first 6 numbers.
In the first way you also have to prove this by induction
Not necessary. No matter what way you use for solving the problem, all you have to do for a legitimate formal proof is to show that the closed form solution: a_n=(5-n) 2^n satisfies the recurrence relation: a_n=2a_(n-1)-2^n, which is trivial:
a_n = (5-n) 2^n = (5-(n-1)-1) 2^n = (5-(n-1)) 2^n - 2^n
= 2 ( (5-(n-1)) 2^(n-1) ) - 2^n
= 2a_(n-1) - 2^n
I so wish you had a bigger board lol. I would love to have each method from start to end in one space.
Where is the bonus method?
hey I thought it was a "differential" equation
sir in the previous video of inverse trigo, why we can't just used the formula?
Pranav Nadda Which formula?
the arctan formula
Yes sir
Thats nice but, how can you solve a recurrence relation where An depends of every previous values?
For example when you have A0=1; An=sum(from k=0 to n-1) of Ak
Obviously i know the solution for this example but i dont know a systematic method to solve it
Rodrigo Lopez The systematic way of doing it is by turning the equation into a difference equation. For example, you said A(n) = Σ{k -> [0, n - 1]; A(k)}, with A(0) = 1. This implies that A(n + 1) = Σ{k -> [0, n]; A(k)}, which in turn implies A(n + 1) - A(n) = [A(n) + A(n - 1) + ••• + A(1) + A(0)] - [A(n - 1) + ••• + A(1) + A(0)] = A(n). The equation A(n + 1) - A(n) = A(n) can now be solved fairly easily. Of course, if the summation has each A(k) with a more complicated coefficient, then instead of simply subtracting A(n) from A(n + 1), you may need to subtract more multiples or do something of the sort, but the essence is there. The reason this is called a difference equation is because A(n + 1) - A(n) := Δ[A(n)], where Δ is the forward difference operator, the discrete analogue of the derivative. The equation you are solving is really Δ[A(n)] = A(n).
Hi I need to solve a(n) = a(n-1) + (2/(n-2k+1)) * a(n-k) + 1. Can somebody help me
Bro just started yappin bout differential equations
Z transform is also possible
3:45 Thanks! I hate it!
im not crying, youre crying
4 examples that are neither of the 2 ways my class wants
cool
No Z-transform?
I did this Pikachu way! YAY!
actually its a arithmetico geometic progression
22:11
At first I thought the video was paused. ^_^