how to solve a recurrence relation (3 ways + 1 bonus)

Подписаться 1,3 млн

Просмотров 133 тыс.

50% 1

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

Опубликовано:

26 июн 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 198

@blackpenredpen 4 года назад

Pikachu was throwing shade. His way doesn't always work.

@mahmoudsamir3528 4 года назад

How cancel I contact with you?

@jagatiello6900 4 года назад

Pikaaaaa (with lightning strikes)

@krishnakumarsah632 4 года назад

How can I differentiate and integrate Riemann ζ function

@jli0108 4 года назад

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

@lelouchlemprouge6380 4 года назад

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

@yopxy6188 4 года назад

Son of blackpenredpen In a few years: 3 ways to solve te Riemann hypothesis.

@blackpenredpen 4 года назад

Lol

@mrocto329 2 года назад

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 Год назад

@@mrocto329 claim your $1M prize then

@mrocto329 Год назад

@@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.

@anon1963 Год назад

@@mrocto329 same here. I formulated the theory of everything and proved it but sadly my dog ate the papers.

@abidhossain8074 4 года назад

To understand recursion you need to understand recursion

@blackpenredpen 4 года назад

LOLLLLL

@Albkiller22 4 года назад

You need to understand the principle of induction lol

@aayushpaswan2941 2 года назад

intresting fun fact: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-YIs3th01NV0.html

@Acute_Angle 4 года назад

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ⁿ

@blackpenredpen 4 года назад

Wow this is neat!

@aayushpaswan2941 2 года назад

intresting fun fact: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-YIs3th01NV0.html

@Robin-Dabank696 12 дней назад

Wait I think there should be a 2 after the equals sign in the first line

@Acute_Angle 12 дней назад

@@Robin-Dabank696 thanks for pointing out

@afrolichesmain777 4 года назад

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!

@blackpenredpen 4 года назад

Thanks!!!

@kgkcStudios 3 года назад

I love how I can learn better from a man dressed as pikachu than I can a professor in a suit.

@kingscreed1511 3 года назад

Probably bc you can actually stay awake with this guy

@SyberMath 3 года назад

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. 💖

@sqfx744 3 года назад

Amazing! You are a genius and look like you're having a blast teaching us. We need more teachers like you!

@szebest 4 года назад

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

@angelmendez-rivera351 4 года назад

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.

@xxxprawn8374 4 года назад

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

@technoguyx 4 года назад

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".

@geometrydashmega238 4 года назад

Excuse me I'm not very familiar with D operator or I might've missed something... What is the 'exploiting the product rule' part?

@angelmendez-rivera351 4 года назад

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.

@aayushpaswan2941 2 года назад

intresting fun fact: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-YIs3th01NV0.html

@andypantoja1628 4 года назад

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

@cuboid2630 4 года назад

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.

@dianayepes3242 3 года назад

Thank you soooo much I haven't been to lectures and you saved me! :D

@Gentrolosiut0 4 года назад

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 👍👍😜😜😜👍👍👍

@egillandersson1780 4 года назад

A new field of study for me. Thank you.

@jancerlima1183 4 года назад

Thanks for your videos man, you help me a lot. Thanks

@trent_tsu 2 года назад

真好，终于看到了微分方程和差分方程对比的vid，谢谢

@aravinds3846 Год назад

Thank you so much for this !!

@00Kie00 2 года назад

I like your style and enthusiasm

@williamadams137 4 года назад

The third solution was very nice.

@harpiasan2885 3 года назад

great explanation! thank you

@latt.qcd9221 4 года назад

Solving recurrence relations was probably the most fun aspect of solving differential equations when I took the course back in college.

@Mr5nan 4 года назад

i love your pikachu way! You can also use Z-transformation in the control theory to solve this as well

@OthmanAlikhan 3 года назад

Thanks for the video =)

@jeffreystockdale8292 3 года назад

Love this guy

@shmuelzehavi4940 4 года назад

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 ?

@matthewstevens340 4 года назад

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

@meghnachaudhury8013 Год назад

Wow so interesting!

@MizardXYT 4 года назад

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

@shmuelzehavi4940 4 года назад

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.

@benjaminbrady2385 4 года назад

Can you link to Peyam and your videos that you referred to at 11 minutes?

@manja5198 4 года назад

I remember learning this through the holy book Boyce DiPrima Differential equations

@6099x 4 года назад

am i the only one who gets comedic value out of this as well? BPRP is hilarious

@kuldeepmathematics1284 4 года назад

Nice. Video.. Sir u r really great teacher

@thedoublehelix5661 4 года назад

This video is amazing!!! Can you do a non linear recurrence relation next?

@angelmendez-rivera351 4 года назад

The Double Helix Someone in the comments suggested the following non-linear recurrence relation problem: a(n + 1) = floor[1.3·a(n)] + 1.

@aayushpaswan2941 2 года назад

intresting fun fact: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-YIs3th01NV0.html

@user-nt9mt5br1q 4 года назад

THANK YOU FOR THE AVATAR!!!!!!!!!

@shohamsen8986 4 года назад

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

@blackpenredpen 4 года назад

Yup that’s what pikachu did at the end : )

@shohamsen8986 4 года назад

I Like Pikachu and his method... :P

@aayushpaswan2941 2 года назад

intresting fun fact: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-YIs3th01NV0.html

@novaje226 4 года назад

recurrence equations are my favorite

@housamkak646 4 года назад

This vid is awesome

@sylvio1687 4 года назад

great are you from usa or singapore?

@pkmath12345 4 года назад

I remember the time when I was a college student working for all those ugly patterns recurrence problems~ Memory flashing back haha

@DiegoMathemagician 4 года назад

For an explicit form of the Fibonacci sequence, you can use Binet's Formula (i've just find it. It is pretty neat!)

@angelmendez-rivera351 4 года назад

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.

@DiegoMathemagician 4 года назад

@@angelmendez-rivera351 he actually made a hidden video lol ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-UrROAw-Ngxs.html

@Steven-ov4no 3 года назад

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.

@holyshit922 4 года назад

Similar to the third method is Z transformation Summation factor also works for this equation

@jackwheel2423 4 года назад

Incredible

@__shubham__ 4 года назад

0:01 that sad mood I cried on.

@jasonduong5167 4 года назад

4th way is using matrices

@arsilvyfish11 4 года назад

This is not geometric... This is not arithmetic... THIS IS NOT NICE! 😂 This is an arithmetico-geometric progression

@vaginalarthritis1753 4 года назад

By the GODS, what fortuitous timing!

@blackpenredpen 4 года назад

@vaginalarthritis1753 4 года назад

@@blackpenredpen lol my professor gave us assignment with solving linear homogeneous recurrence relations. Its taken some time but I appreciate any approach I find :)

@blackpenredpen 4 года назад

Ah i see!! Best of luck!! Those are fun stuff!

@vaginalarthritis1753 4 года назад

@@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!

@arsilvyfish11 4 года назад

@Dr.Peyam explained to solve the 2nd order differential without guessing!!! Bprp: bruh

@Mario_Altare 4 года назад

Excellent! I miss the previous blackboard...

@dominiquefortin5345 4 года назад

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).

@user-nt9mt5br1q 4 года назад

You are blackpenredpenbluepen now

@holyshit922 Год назад

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

@saurabhpal9505 4 года назад

Sir can you make video on inverse Laplace transform of 1/sqrt(s)

@yesidlee 4 года назад

Power Series joke killed me

@christosdelivasilis 4 года назад

Can you explain the Simplex algorithm in a video?

@stapler942 2 года назад

The beginning of my algorithms class involved solving recurrence relations. The Master Theorem could make a great video btw!

@blackpenredpen 2 года назад

What’s the master theorem?

@stapler942 2 года назад

@@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.

@carstenmeyer7786 4 года назад

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?"

@madhabkumar9687 3 года назад

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

@sphakamisozondi 4 года назад

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. 🤣

@shambosaha9727 4 года назад

Tell math jokes. It works!

@holyshit922 Год назад

30:18 Believe me here it is better to start indexing from zero and then multiply both sides of equation by x

@Nerketur 4 года назад

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!

@adnanahmad2549 3 года назад

10TH GRADER'S MIND:"KABOOOOOOM!!!!" NICE VIDEO

@ShazNoman 3 года назад

Can we solve this question by characteristics root method? Please explain this type of question by characteristics root method. Thanks 👍👍

@luisguilhermecoelho9954 4 года назад

What about the cases that the recurrence relation isn't linear?

@kishanhariyani9523 4 года назад

How can integrate (e^x/x)dx

@orenfivel6247 3 года назад

Generating Function is similar to Z transform w/ x=z^-1, and Z transform may be easier to solve with...

@yoshuayonatan1538 4 года назад

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.

@mahendragupta2896 4 года назад

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

@blackpenredpen 4 года назад

Oh nice. And I think that’s similar to what pikachu did at the end of the video.

@anuragjuyal7614 4 года назад

At 30:21 shouldn't the derivative be -1/(1-x)^2

@trdi 4 года назад

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

@curtiswfranks 4 года назад

"Our favorite constant: c." (Paraphrased for presentation) xD

@steve2817 4 года назад

40min video at 9:51 am very good ;)

@SakanaKuKuRu 4 года назад

Imagine this as an Olympiad question but they ask you to figure out the general term given the first 6 numbers.

@sea34101 4 года назад

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

@shambosaha9727 4 года назад

bruh

@suhailawm 4 года назад

tnx alot. last method. Penalty Goal # Fantanstic

@eliasabi-elias8501 4 года назад

24:30 how do you know |X| < 1? I thought the infinite geometric series doesn't converge if this condition is not satisfied?

@yuvalid4156 4 года назад

You do not care about it's convergence. X is arbitrary, and as such you can assume that the sum converges.

@kyleneilson1457 4 года назад

What happened to your video after this? I saw it, but did not have a chance to watch it, and now it is gone.

@paladin80lvl 2 года назад

Can you solve this? T(n) = T(n - 1) + cn, if n > 1 T(1) = 0

@hari8568 4 года назад

Z transform is also possible

@chronos_3144 4 года назад

In the first way you also have to prove this by induction

@shmuelzehavi4940 4 года назад

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

@secular7171 4 года назад

Sir, can you please suggest me book for special function for physics I am in final sems of Master of science in physics.

@secular7171 4 года назад

Here, sir you can mail me rs.rahulsinghtu@gmail.com I will highly thankful of you

@pranav6352 4 года назад

sir in the previous video of inverse trigo, why we can't just used the formula?

@angelmendez-rivera351 4 года назад

Pranav Nadda Which formula?

@blackpenredpen 4 года назад

the arctan formula

@pranav6352 4 года назад

Yes sir

@senku5497 2 года назад

22:11

@williamadams137 4 года назад

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?

@angelmendez-rivera351 4 года назад

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.

@angelmendez-rivera351 4 года назад

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.

@angelmendez-rivera351 4 года назад

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.

@angelmendez-rivera351 4 года назад

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.

@williamadams137 4 года назад

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.😅

@seraphikimercury4921 4 года назад

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.

@seraphikimercury4921 4 года назад

I used to work for tcc. You are in eastern Washington right? Scc was it?

@knightwik 4 года назад

@@seraphikimercury4921 oh ok

@aayushpaswan2941 2 года назад

intresting fun fact: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-YIs3th01NV0.html

@drachaksakcha 4 года назад

3:45 Thanks! I hate it!

@user-ye9oh7ip1z 4 года назад

hey I thought it was a "differential" equation

@smartgeek3000 3 года назад

im not crying, youre crying

@aryanshrivastav7418 4 года назад

actually its a arithmetico geometic progression

@rodrigolopez3874 4 года назад

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

@angelmendez-rivera351 4 года назад

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).