Can't respond directly, so I hope you see this Iban Ariza, If the last digit is 0 or 1, then you can do anything. (so 2g(n-1)) If the last digit is 2, then you can't have 10 preceding it, but you can have anything else, like 00,01,11,20,02,12,21,22.
Hi Trev, thanks for the informative and clear video, I was just wondering though what is the alpha and beta technique called so I can look up more theory stuff on it. Thank you.
Amazing video so helpful :) just wanted to let you know that there was a slight mistake around 17:00 it should have been alpha sub k times n to the k-1 three to the n and similar for beta so beta sub m times n to the n-1. Great video again :)
Thank you so much. I can't believe how much money I'm paying my university, and all they do to teach us is "Theorem x: , Proof:" over and over again with no actual explanation as to what is going on. All the while this content is free on youtube
Hey Trev, I might have missed something, but in your explanation of having the same roots and all, shouldn't the last term be alpha * n ^ (k-1)? Apologies if i'm unclear, I'm not sure how to type out an expression. But yeah, am I supposed to count the number of roots starting from 0 or 1?
Lets say that we are looking for the number g(n) of ternary strings of length n that do not contain 102 as a substring. How would you approach this problem? If the last digit is {0,1,2} then, you can have any value for g(n-1) (either 0,1,2), so 3g(n-1). Also, if the second to last digit contains a {1,2}, then you can have any value for g(n-2) {0,1,2} so it would be g(n-2) 3 times. However, if you have the last two digits be 02, then you cannot have 1 on the prior term to those two and so it would result in 2g(n-3). So the recurrence relation would be 3g(n-1)+3g(n-2)+2g(n-3)? I know it is probably wrong. How would you solve it?
at 1:17, the equation should be a(n) - a(n-1) = kn and the solution should be a(n) = c + E(k*i) instead of E(k) Please Rectify. Do tell me if I'm wrong though, or if I have misunderstood anything.
A derivation of the form of the solution given roots of the characteristic polynomial would be nice. Does this require z-transforms and Cauchy's residue theorem? Or is there an easier way? I suppose there is always guess and check.
hello. I think there is a problem in the bit example. The a1 should be 2 as there can be a 1 or 0. a2 can be (00 01 10) so there can be 3 a2. This means that first is 2 and the second is 3 than you can find the rest of the examples from there. for example a3 is 5 and a4 is 8 and a5 is 13. Hope this helps everyone that is training for their exams and thanks for the video!
If the (n-1)th is 0,Can first n-2 positions be anything they want? . There can be consecutive 1s in first n-2 positions. Isnt it?(regarding “= an-1 + an-2”)
4:12 to 4:32 really just took off. No idea what's happening there. We didn't follow any of the processes that were just established. Edit: Okay, I see. We just did the entire thing completely backward. Now, I need a Trev video for how to factor.
I'm a little unclear when you say that for anything else a(n-1), you can order it however you want. Say the last number in the binary string is 0. You say that for a(n-1), we can order it however we want. But that's not exactly true, because if we order, say, a length 5 binary string as 10110, that's clearly not allowed because there's two consecutive 1s. Could someone clarify this for me?
Way late to the party, but for anyone else with this question: a value denoted by a(n) always refers to the amount of "right" ways that the n elements can be organized. That is to say, the number of ways that a string of n binary elements with no consecutive ones can be created equals a(n). So a(n-1) is simply the amount of "correct" strings of n-1 binary elements.
can someone explain why if the string ends with 0 theres an-1 ways of making the strings? i get why it's an-1 but doesn't it have to count for the strings that dont have consecutive 1s?
sir can We take the chareterstic polynomial in reverse In Ur example You have Shown r square minus r minus 6 so Can we tak in reverse Like -6square minus 1 plus 1 ?? Iz It correct ?
For the second example, a[n]-4a[n-1]+4a[n-2]=0, a[0]=1 a[1]=3. Using this equation, a[2]-4(3)+4(1)=0, so a[2]-8=0, or a[2]=8. Using the equation a[n] = 2^n (1+(1/2)n), a[2] = 2^(2) (1+(1/2)2) = 4(2) = 8. So both are the same answer. Be careful with the homogeneous systems as you may flip your signs when looking at the original equation.
probably to make it more clear that the sign changes with the power. It can be easier to recognize if it is written like (-2)^n instead of (-2^n), especially if your attention is focused on the harder parts of the problem.
In the final problem, I am finding the answer that you have posted *(-1). I do this a lot as a mistake, but I can't find the specific error in this case. Maybe someone can confirm error? In any case, thank you very much for these lessons.
"Terms sum to zero." Same as homogeneous differential equations. There is no forcing function involved. The response (sequence) depends only on the recurrence relation (characteristic equation) and the initial conditions.
th-cam.com/video/7mhvA5L7KqY/w-d-xo.html when you wirte the formula for An for same roots, shouldn't it be Lk.(n^(k-1)).3^n? just a bit confused, because if it's n^k, then the first one, where we have L1 (sorry i don't have alpha) we are going to have n^1 instead of n^0 ?
![[Discrete Mathematics] Homogeneous Recurrence Relations Examples](http://i.ytimg.com/vi/Otj2ypYXn0Q/mqdefault.jpg)
![[Discrete Mathematics] Homogeneous Recurrence Relations Examples](/img/tr.png)
dude at 16:31,there's an error-the last term should have the power "k-1",and not "k"
I was going to comment the same thing. I think he knows the answer and just made a small error there.
I thoght the same
Yup noticed it too.....
Exactly! You are right
4 years later and yeah that's an error.
I studied this just one night before exams and understood very well. Thanks for the tutorial bro
Awesome tutor. You are saving lives around the world and making demystifying rather seemingly complex concepts. Thank you very much
Can't respond directly, so I hope you see this Iban Ariza,
If the last digit is 0 or 1, then you can do anything. (so 2g(n-1))
If the last digit is 2, then you can't have 10 preceding it, but you can have anything else, like 00,01,11,20,02,12,21,22.
Hi Trev, thanks for the informative and clear video, I was just wondering though what is the alpha and beta technique called so I can look up more theory stuff on it. Thank you.
"this is more of a mechanics guide, rather than a theoretical guide" THANK YOU! All I can find about this is theory's about fibonacci lol
What a lifesaver it was to find this video < 2 days before my final, phew
Best damn tutor I have been watching so far, really helped me get ready for my discrete final.
This worked, the first 9 minutes had the explanations I was looking for.
Amazing video so helpful :) just wanted to let you know that there was a slight mistake around 17:00 it should have been alpha sub k times n to the k-1 three to the n and similar for beta so beta sub m times n to the n-1. Great video again :)
Joshua Uwaifo*times n to the m-1
+Joshua Uwaifo Was thinking the same thing too. Good observation.
I think you're right!
Thank you so much. I can't believe how much money I'm paying my university, and all they do to teach us is "Theorem x: , Proof:" over and over again with no actual explanation as to what is going on. All the while this content is free on youtube
20:13 a0=1, a1=2 I used these parameters to calculate Fibonacci number which took me a while to figure why I was wrong.
Great! I'm watching this after 8 years.
You're not alone
Holy shit! Thank you!
What you explained in 3 minutes (the characteristic polynomial) took my professor 25 mins to explain!
Correct dude😅
Thank you so so much, my exam is tomorrow and if I do well it's all thanks to you, I wish you the best!
Hey Trev, I might have missed something, but in your explanation of having the same roots and all, shouldn't the last term be alpha * n ^ (k-1)?
Apologies if i'm unclear, I'm not sure how to type out an expression.
But yeah, am I supposed to count the number of roots starting from 0 or 1?
You are correct
Free and easy-to-understand lessons, this is the guy who contributes to evolution by passing down knowledge to generations without any financial cost
Wow good biological perspective, I never thought about it that way
yes, same for m at 17:22 the last beta term should have "n" to the power of "m-1"
"ok, we have some room here, let's use this room" instead of "ok we will use the next page" hahaha typical Maths person :DD
This was a freaking brilliant video. You explained in a vastly superior way than the way my notes did
Thanks a lot, Sir, your explanations were clear and I understood the work! @Stellenbosch University & UNISA.
Damn bro......! You are definitely a life saver.... before my exams....thank you bro....!
for same root:
An= alpha(k) * n^(k-1) * (3)^n
Tyson Tamang yep
thank you from the bottom of my heart
Lets say that we are looking for the number g(n) of ternary strings of length n that do not contain 102 as a substring. How would you approach this problem?
If the last digit is {0,1,2} then, you can have any value for g(n-1) (either 0,1,2), so 3g(n-1). Also, if the second to last digit contains a {1,2}, then you can have any value for g(n-2) {0,1,2} so it would be g(n-2) 3 times. However, if you have the last two digits be 02, then you cannot have 1 on the prior term to those two and so it would result in 2g(n-3). So the recurrence relation would be 3g(n-1)+3g(n-2)+2g(n-3)? I know it is probably wrong. How would you solve it?
You are totally AWESOME thank you so much for this series teachers like you are unique I hope you will post more videos in future thank you so much
16:43, isn't the kth term on the right supposed to have n raised to the power of k-1 instead of k?
Yes. It's would be k - 1
at 1:17, the equation should be a(n) - a(n-1) = kn
and the solution should be a(n) = c + E(k*i) instead of E(k)
Please Rectify.
Do tell me if I'm wrong though, or if I have misunderstood anything.
This is very helpful. But what happens if the roots are complex(imaginary)? Do we introduce sin/cos in the solution?
Thanks allot man, you're really good at explaining stuff
Learn a lot from this tutorial
Clear and too the point explanation, Great Job :-)
thank you so much for making this tutorial :)
wow it really really magic you saved my grade ,and time
i can not thank u enough ur a hero
Hi Trev,
Can you go over the algebra for when r= (1+- sq(5))/2
Thanks pal! This is just awesome.
Thank you so much.. your explanations better than my teacher lol
love u man thank u so much for giving us free knowledge
Thankyou thus helped a lot
Thank you very much. Your videos are very helpful.
Thank you for the videos. May I ask what app/software you use?
Thanks a lot 😄
21:00 classic dp problem... nice...!
you are the BEST !
Don't you think a0 should be 0 here at 20:10 because the string length is 0 hence we can't have anything of length of 0. Appreciate you response!
Yeh Im confused with that aswell, it's been 10 months, do you know the answer now? :)
@@PedroMiguel-iw5ul It’s been 5 years, have you figured it out yet?
thank you so much from turkey
thanks so much...literally saved my existence.
A derivation of the form of the solution given roots of the characteristic polynomial would be nice.
Does this require z-transforms and Cauchy's residue theorem? Or is there an easier way? I suppose there is always guess and check.
great video, was very helpful
dude you are best
hello. I think there is a problem in the bit example. The a1 should be 2 as there can be a 1 or 0. a2 can be (00 01 10) so there can be 3 a2. This means that first is 2 and the second is 3 than you can find the rest of the examples from there. for example a3 is 5 and a4 is 8 and a5 is 13. Hope this helps everyone that is training for their exams and thanks for the video!
love ur handwriting
Great video sir.. Thank You.
Why do you multiply the first equation twice at 7:25?
I know this is 9 months late, but for anyone else wondering the same thing. It's to cancel out the Beta to get A on its own.
Find the solution to the recurrence relation an =6an-1 +11an-2 -6an-3 with a0=2, a1=5 and a2=15.
Thanks! This vid really helped! :)
What will the form of An if we get imaginary roots?
Thank you so much!
so helpful thank you
Thank you..
At 17:19 the alpha and beta should start at alpha0 and beta 0 not alpha1 and beta 1.. right??? someone answer ...
If the (n-1)th is 0,Can first n-2 positions be anything they want? . There can be consecutive 1s in first n-2 positions. Isnt it?(regarding “= an-1 + an-2”)
thank you very much :)
Amazing, thank u
Thankyou very much Sir
very much helpful
Got it😇😇😇👏👏👏👏
can someone tell me (7:00) why he put 1 instead of 8 when a1 is basically 8 ?
what would be the characteristic eqn of : An = 2An-1 - 2An-2 ??
its x^2 - 2x + 2 = 0 right?
but soln in my book and on site it says x^2 - 2x - 2 = 0
what does that mean by the part "how many ways can we have zero?" at 20:04 ??
help me
I was hoping for when we have 3 roots how can we solve for the Constant coffeciants :/ still this made it more clear so thank you.
simply evaluate a0, a1, a2, now 3 equation and 3 unknown, the solve
4:12 to 4:32 really just took off. No idea what's happening there. We didn't follow any of the processes that were just established.
Edit: Okay, I see. We just did the entire thing completely backward.
Now, I need a Trev video for how to factor.
there is a mistake at 16:41, shouldn't it be (alpha)k*nˆ(k-1) instead of (alpha)k*nˆk
I'm a little unclear when you say that for anything else a(n-1), you can order it however you want. Say the last number in the binary string is 0. You say that for a(n-1), we can order it however we want. But that's not exactly true, because if we order, say, a length 5 binary string as 10110, that's clearly not allowed because there's two consecutive 1s. Could someone clarify this for me?
Basically he means that you can place any number(n-1) at that particular place,not the whole number.
Way late to the party, but for anyone else with this question: a value denoted by a(n) always refers to the amount of "right" ways that the n elements can be organized. That is to say, the number of ways that a string of n binary elements with no consecutive ones can be created equals a(n). So a(n-1) is simply the amount of "correct" strings of n-1 binary elements.
can someone explain why if the string ends with 0 theres an-1 ways of making the strings? i get why it's an-1 but doesn't it have to count for the strings that dont have consecutive 1s?
Does the order of roots matter when we apply them to the formulas? I am a little bit confused, any explanation appreciated!
It's not a problem because at that time the alpha and beta values changes. And finally balance that formula
Awesome!
sir can We take the chareterstic polynomial in reverse In Ur example You have Shown r square minus r minus 6 so Can we tak in reverse Like -6square minus 1 plus 1 ?? Iz It correct ?
plss Do Reply
I'm not quite sure what you're asking, but I've never seen it done that way and I don't think it would work.
Which software are you using?
I was using Windows Journal when this video was recorded. I use PDF Annotator now. (+ OBS for screen recording)
16:15 - Why is it not n to the (k-1)?
Why at 13:40 it is 2 to the n plus n 2 to the n-1? where the n-1 came from?
He's just using exponent properties here.
1/2 is the same thing as saying 2^-1
2^-1 * 2^n = 2^(n-1)
where can i find the proof for the formula ( a_n = alpha(3^n) +beta(-2^n) ???? plz help[
I want to ask why is if the r = 3 only. Then we must write C1 (3^n) + C2 n(3^n). Why is there an n in the second C
Can you please eli5 the bit string problem?
is a0 taken as 0 instead of 1? because alpha=1/√5 and beta=-1/√5 is only attainable in that condition...Am I missing something?
Is it possible for alfa and beta to be the same value?
this video is very useful to me because i have a exam on Monday i hope i write exam well
Legendary!
I fucking love you man! Because of you I am gonna pass my CA2!
Hey!! Did you?
Why is it that for the second example, A(2) isn't the same answer for the recurrence relation equation and for the homogeneous equation?
For the second example, a[n]-4a[n-1]+4a[n-2]=0, a[0]=1 a[1]=3. Using this equation, a[2]-4(3)+4(1)=0, so a[2]-8=0, or a[2]=8. Using the equation a[n] = 2^n (1+(1/2)n), a[2] = 2^(2) (1+(1/2)2) = 4(2) = 8. So both are the same answer. Be careful with the homogeneous systems as you may flip your signs when looking at the original equation.
god bless u
Great tutorial but what if the an is squared already?
Hello sir ,this can not be solved using Generating Functions?
+samuel jawahar Yes, but it is not introduced in the series until a few videos later.
thanks a lot sir ,may i know the subject i should know to solve "stackoverflow.com/questions/11382189/number-of-ways-to-place-kings-on-chess-board"
Is there a reason that at step 3 that the bracket placement differs per term?
I'm not sure what you mean here.
I think he's talking about 5:26, where An = alpha(3^n) + beta(-2)^n
Yeah
probably to make it more clear that the sign changes with the power. It can be easier to recognize if it is written like (-2)^n instead of (-2^n), especially if your attention is focused on the harder parts of the problem.
GOAT!!!
In the final problem, I am finding the answer that you have posted *(-1). I do this a lot as a mistake, but I can't find the specific error in this case. Maybe someone can confirm error?
In any case, thank you very much for these lessons.
The mistake is in the premise that a0 = 0.
In Fibonacci a0 = a1 = 1.
The answer written there is only attainable with the correct initial conditions.
16:50 daggara wrong bayya.....nth relation.....alpha(k)*n(k-1) correct
how do you describe a homogeneous recurrence relation with words?
"Terms sum to zero." Same as homogeneous differential equations. There is no forcing function involved. The response (sequence) depends only on the recurrence relation (characteristic equation) and the initial conditions.
How do you solve T(n)=Theta(n)+4T(n/16)+4T(n/6)+8T(n/16)
for the Fibonacci series solution..... do we take a0 = 1 and a1 =1 or do we take a0 = 1 and a1=2?
Fibonacci technically starts at a_0=1 and a_1=1. The Lucas sequence starts at a_0=1 and a_1=2, even though they're both basically the same.
th-cam.com/video/7mhvA5L7KqY/w-d-xo.html
when you wirte the formula for An for same roots, shouldn't it be Lk.(n^(k-1)).3^n? just a bit confused, because if it's n^k, then the first one, where we have L1 (sorry i don't have alpha) we are going to have n^1 instead of n^0 ?