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
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.
@@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.
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ⁿ
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 👍👍😜😜😜👍👍👍
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
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.
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
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
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
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.
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
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.
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.
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).
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.
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.
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
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
@@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.
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?"
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 ?
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
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
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.
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.
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!
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).
Completely off topic but this guy broke my calculator! I let my brother use it for a test for this guys class and he did did a factory test on everyone calculators. My it84 now only graphs circles no matter what input I have........ idk why prof here thinks he is allowed to tamper with students personal stuff but I haven’t figured out after 1 semester later how to fix it!!!! Any ideas ? Do I have to send it in for repairs ? I’ve googled how to do a rest and it didn’t work
Generating function is also regarded as a formal series. You can define algebra on generating series to be as usual and differentiating to behave as usual.
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: ua-cam.com/video/YIs3th01NV0/v-deo.html
Wait I think there should be a 2 after the equals sign in the first line
@@Robin-Dabank696 thanks for pointing out
Amazing
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!!!
To understand recursion you need to understand recursion
LOLLLLL
You need to understand the principle of induction lol
intresting fun fact: ua-cam.com/video/YIs3th01NV0/v-deo.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
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 👍👍😜😜😜👍👍👍
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: ua-cam.com/video/YIs3th01NV0/v-deo.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
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!
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: ua-cam.com/video/YIs3th01NV0/v-deo.html
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.
The third solution was very nice.
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
真好，终于看到了微分方程和差分方程对比的vid，谢谢
Thanks for your videos man, you help me a lot. Thanks
I like your style and enthusiasm
A new field of study for me. Thank you.
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: ua-cam.com/video/YIs3th01NV0/v-deo.html
Thank you soooo much I haven't been to lectures and you saved me! :D
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.
i love your pikachu way! You can also use Z-transformation in the control theory to solve this as well
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 ua-cam.com/video/UrROAw-Ngxs/v-deo.html
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).
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.
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.
Solving recurrence relations was probably the most fun aspect of solving differential equations when I took the course back in college.
@Dr.Peyam explained to solve the 2nd order differential without guessing!!!
Bprp: bruh
I remember learning this through the holy book Boyce DiPrima Differential equations
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.
4th way is using matrices
This is not geometric...
This is not arithmetic...
THIS IS NOT NICE!
😂
This is an arithmetico-geometric progression
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
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.
Similar to the third method is Z transformation
Summation factor also works for this equation
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?"
Thank you so much for this !!
Power Series joke killed me
am i the only one who gets comedic value out of this as well? BPRP is hilarious
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 ?
recurrence equations are my favorite
30:18 Believe me here it is better to start indexing from zero
and then multiply both sides of equation by x
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!
great explanation! thank you
Generating Function is similar to Z transform w/ x=z^-1, and Z transform may be easier to solve with...
What happened to your video after this? I saw it, but did not have a chance to watch it, and now it is gone.
Love this guy
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
Nice. Video.. Sir u r really great teacher
0:01 that sad mood I cried on.
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
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
Can we solve this question by characteristics root method?
Please explain this type of question by characteristics root method.
Thanks 👍👍
Can you link to Peyam and your videos that you referred to at 11 minutes?
Excellent! I miss the previous blackboard...
I remember the time when I was a college student working for all those ugly patterns recurrence problems~ Memory flashing back haha
10TH GRADER'S MIND:"KABOOOOOOM!!!!"
NICE VIDEO
You are blackpenredpenbluepen now
THANK YOU FOR THE AVATAR!!!!!!!!!
Where is the bonus method?
Can you explain the Simplex algorithm in a video?
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: ua-cam.com/video/YIs3th01NV0/v-deo.html
Thanks for the video =)
Can you solve this?
T(n) = T(n - 1) + cn, if n > 1
T(1) = 0
I so wish you had a bigger board lol. I would love to have each method from start to end in one space.
Imagine this as an Olympiad question but they ask you to figure out the general term given the first 6 numbers.
hey I thought it was a "differential" equation
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
What about the cases that the recurrence relation isn't linear?
Wow so interesting!
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.😅
At 30:21 shouldn't the derivative be
-1/(1-x)^2
Sir can you make video on inverse Laplace transform of 1/sqrt(s)
Z transform is also possible
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!
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).
"Our favorite constant: c."
(Paraphrased for presentation)
xD
This vid is awesome
Completely off topic but this guy broke my calculator! I let my brother use it for a test for this guys class and he did did a factory test on everyone calculators. My it84 now only graphs circles no matter what input I have........ idk why prof here thinks he is allowed to tamper with students personal stuff but I haven’t figured out after 1 semester later how to fix it!!!! Any ideas ? Do I have to send it in for repairs ? I’ve googled how to do a rest and it didn’t work
actually its a arithmetico geometic progression
great
are you from usa or singapore?
Incredible
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.
Generating function is also regarded as a formal series. You can define algebra on generating series to be as usual and differentiating to behave as usual.
Bro just started yappin bout differential equations
40min video at 9:51 am
very good ;)
No Z-transform?
How can integrate (e^x/x)dx
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
Why not solve this using the Z transform?
I actually don’t know it too well but I will study it more
4 examples that are neither of the 2 ways my class wants
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
tnx alot.
last method.
Penalty Goal # Fantanstic
Hi I need to solve a(n) = a(n-1) + (2/(n-2k+1)) * a(n-k) + 1. Can somebody help me
I have a stupid question Mr. RedPen. Is capital A just a constant... Edit: nevermind, I'm just a little slow following the algebra, my bad...
"if you want to learn how to solve your relationship then watch this video." 🤣😂 yeah!!!!
Loll
Sir which app do you use to make thumbnail?
I am big fan of yours.likewise you i am also lover of mathematics
Will you guide me ?
22:11
3:45 Thanks! I hate it!