Finding Annihilators for Recurrence Relations The 2019 Stack Overflow Developer Survey Results Are Infinding recurrence relationsPredictions for recurrence relationsRecurrence Relations for $c_1$ and $c_2$looking for explanation behind solution for a 1st order recurrence relation.Recurrence relations for $a_n+2$How does one find annihilators for recurrence relations?Recurrence Relations:Finding Recurrence relations for combinatorics problemsFibonacci Recurrence RelationsCharacteristic equation for recurrence relations
Does adding complexity mean a more secure cipher?
Did the UK government pay "millions and millions of dollars" to try to snag Julian Assange?
What is the most efficient way to store a numeric range?
How can I add encounters in the Lost Mine of Phandelver campaign without giving PCs too much XP?
Is it possible for absolutely everyone to attain enlightenment?
A word that means fill it to the required quantity
Will it cause any balance problems to have PCs level up and gain the benefits of a long rest mid-fight?
What do I do when my TA workload is more than expected?
Why was M87 targeted for the Event Horizon Telescope instead of Sagittarius A*?
APIPA and LAN Broadcast Domain
Did any laptop computers have a built-in 5 1/4 inch floppy drive?
How to support a colleague who finds meetings extremely tiring?
Why doesn't shell automatically fix "useless use of cat"?
Correct punctuation for showing a character's confusion
Accepted by European university, rejected by all American ones I applied to? Possible reasons?
Is it okay to consider publishing in my first year of PhD?
What information about me do stores get via my credit card?
How do PCB vias affect signal quality?
The phrase "to the numbers born"?
Cooking pasta in a water boiler
Old scifi movie from the 50s or 60s with men in solid red uniforms who interrogate a spy from the past
Is it ok to offer lower paid work as a trial period before negotiating for a full-time job?
Deal with toxic manager when you can't quit
Are spiders unable to hurt humans, especially very small spiders?
Finding Annihilators for Recurrence Relations
The 2019 Stack Overflow Developer Survey Results Are Infinding recurrence relationsPredictions for recurrence relationsRecurrence Relations for $c_1$ and $c_2$looking for explanation behind solution for a 1st order recurrence relation.Recurrence relations for $a_n+2$How does one find annihilators for recurrence relations?Recurrence Relations:Finding Recurrence relations for combinatorics problemsFibonacci Recurrence RelationsCharacteristic equation for recurrence relations
$begingroup$
Recently I've taken an interest in solving recurrence relations using annihilators but I'm still unclear as to how to find such annihilators.
My professor provides the following linear recurrence in his lecture notes:
$r_i$ = $7r_i-1$ - $16r_i-2$ + $12r_i-3$ with initial conditions $r_0$ = 1, $r_1$ = 5, and $r_2$ = 17
for some reason, the recurrence is converted to:
$r_i+3$ - $7r_i+2$ + $16r_i+1$ - $12r_i$ = 0 and the annihilator found from there.
Could someone please provide some insight as to how the recurrence was converted to this form?
Also there's the matter of actually applying annihilators to recurrence relations themselves. For example, I'm still stumped as to how the annihilator $E^2$ - $E$ - $1$ when applied to the fibonacci recurrence $F_i$ = $F_i-1 + F_i-2$ actually yields a sequence of all o's.
My professor writes: $E^2(F_i)$ - $E(F_i)$ - $F_i$ = $(F_i+2 - F_i+1 - F_i)$ = $(0)$ but the algebra behind said statement remains unclear.
Any clarification would be greatly appreciated.
discrete-mathematics recurrence-relations fibonacci-numbers
asked Apr 1 at 1:41
GraysonGrayson
111
$endgroup$
add a comment |
$begingroup$
Recently I've taken an interest in solving recurrence relations using annihilators but I'm still unclear as to how to find such annihilators.
My professor provides the following linear recurrence in his lecture notes:
$r_i$ = $7r_i-1$ - $16r_i-2$ + $12r_i-3$ with initial conditions $r_0$ = 1, $r_1$ = 5, and $r_2$ = 17
for some reason, the recurrence is converted to:
$r_i+3$ - $7r_i+2$ + $16r_i+1$ - $12r_i$ = 0 and the annihilator found from there.
Could someone please provide some insight as to how the recurrence was converted to this form?
Also there's the matter of actually applying annihilators to recurrence relations themselves. For example, I'm still stumped as to how the annihilator $E^2$ - $E$ - $1$ when applied to the fibonacci recurrence $F_i$ = $F_i-1 + F_i-2$ actually yields a sequence of all o's.
My professor writes: $E^2(F_i)$ - $E(F_i)$ - $F_i$ = $(F_i+2 - F_i+1 - F_i)$ = $(0)$ but the algebra behind said statement remains unclear.
Any clarification would be greatly appreciated.
discrete-mathematics recurrence-relations fibonacci-numbers
asked Apr 1 at 1:41
GraysonGrayson
111
$endgroup$
$begingroup$
Welcome to Math Stack Exchange. Replace $i$ with $i+3$
$endgroup$
– J. W. Tanner
Apr 1 at 1:52
$begingroup$
As for converting the recurrence, he just substituted $i+3$ in place of $i$. Your second question confuses me. Do you understand what the $E$ operator does? $E^2 F_i-E F_i-F_i= F_i+2-F_i+1-F_i$ by definition of the operator. That this is identically $0$ is just the definition of the Fibonacci numbers.
$endgroup$
– saulspatz
Apr 1 at 1:55
$begingroup$
I'm clear as to what the $E$ operator does, I'm just confused as to how it is identical to 0.
$endgroup$
– Grayson
Apr 1 at 2:00
add a comment |
$begingroup$
Recently I've taken an interest in solving recurrence relations using annihilators but I'm still unclear as to how to find such annihilators.
My professor provides the following linear recurrence in his lecture notes:
$r_i$ = $7r_i-1$ - $16r_i-2$ + $12r_i-3$ with initial conditions $r_0$ = 1, $r_1$ = 5, and $r_2$ = 17
for some reason, the recurrence is converted to:
$r_i+3$ - $7r_i+2$ + $16r_i+1$ - $12r_i$ = 0 and the annihilator found from there.
Could someone please provide some insight as to how the recurrence was converted to this form?
Also there's the matter of actually applying annihilators to recurrence relations themselves. For example, I'm still stumped as to how the annihilator $E^2$ - $E$ - $1$ when applied to the fibonacci recurrence $F_i$ = $F_i-1 + F_i-2$ actually yields a sequence of all o's.
My professor writes: $E^2(F_i)$ - $E(F_i)$ - $F_i$ = $(F_i+2 - F_i+1 - F_i)$ = $(0)$ but the algebra behind said statement remains unclear.
Any clarification would be greatly appreciated.
discrete-mathematics recurrence-relations fibonacci-numbers
asked Apr 1 at 1:41
GraysonGrayson
111
$endgroup$
Recently I've taken an interest in solving recurrence relations using annihilators but I'm still unclear as to how to find such annihilators.
My professor provides the following linear recurrence in his lecture notes:
$r_i$ = $7r_i-1$ - $16r_i-2$ + $12r_i-3$ with initial conditions $r_0$ = 1, $r_1$ = 5, and $r_2$ = 17
for some reason, the recurrence is converted to:
$r_i+3$ - $7r_i+2$ + $16r_i+1$ - $12r_i$ = 0 and the annihilator found from there.
Could someone please provide some insight as to how the recurrence was converted to this form?
Also there's the matter of actually applying annihilators to recurrence relations themselves. For example, I'm still stumped as to how the annihilator $E^2$ - $E$ - $1$ when applied to the fibonacci recurrence $F_i$ = $F_i-1 + F_i-2$ actually yields a sequence of all o's.
My professor writes: $E^2(F_i)$ - $E(F_i)$ - $F_i$ = $(F_i+2 - F_i+1 - F_i)$ = $(0)$ but the algebra behind said statement remains unclear.
Any clarification would be greatly appreciated.
discrete-mathematics recurrence-relations fibonacci-numbers
discrete-mathematics recurrence-relations fibonacci-numbers
asked Apr 1 at 1:41
GraysonGrayson
111
asked Apr 1 at 1:41
GraysonGrayson
111
asked Apr 1 at 1:41
GraysonGrayson
111
asked Apr 1 at 1:41
GraysonGrayson
111
asked Apr 1 at 1:41
GraysonGrayson
111
111
$begingroup$
Welcome to Math Stack Exchange. Replace $i$ with $i+3$
$endgroup$
– J. W. Tanner
Apr 1 at 1:52
$begingroup$
As for converting the recurrence, he just substituted $i+3$ in place of $i$. Your second question confuses me. Do you understand what the $E$ operator does? $E^2 F_i-E F_i-F_i= F_i+2-F_i+1-F_i$ by definition of the operator. That this is identically $0$ is just the definition of the Fibonacci numbers.
$endgroup$
– saulspatz
Apr 1 at 1:55
$begingroup$
I'm clear as to what the $E$ operator does, I'm just confused as to how it is identical to 0.
$endgroup$
– Grayson
Apr 1 at 2:00
add a comment |
$begingroup$
Welcome to Math Stack Exchange. Replace $i$ with $i+3$
$endgroup$
– J. W. Tanner
Apr 1 at 1:52
$begingroup$
As for converting the recurrence, he just substituted $i+3$ in place of $i$. Your second question confuses me. Do you understand what the $E$ operator does? $E^2 F_i-E F_i-F_i= F_i+2-F_i+1-F_i$ by definition of the operator. That this is identically $0$ is just the definition of the Fibonacci numbers.
$endgroup$
– saulspatz
Apr 1 at 1:55
$begingroup$
I'm clear as to what the $E$ operator does, I'm just confused as to how it is identical to 0.
$endgroup$
– Grayson
Apr 1 at 2:00
$begingroup$
Welcome to Math Stack Exchange. Replace $i$ with $i+3$
$endgroup$
– J. W. Tanner
Apr 1 at 1:52
$begingroup$
Welcome to Math Stack Exchange. Replace $i$ with $i+3$
$endgroup$
– J. W. Tanner
Apr 1 at 1:52
$begingroup$
As for converting the recurrence, he just substituted $i+3$ in place of $i$. Your second question confuses me. Do you understand what the $E$ operator does? $E^2 F_i-E F_i-F_i= F_i+2-F_i+1-F_i$ by definition of the operator. That this is identically $0$ is just the definition of the Fibonacci numbers.
$endgroup$
– saulspatz
Apr 1 at 1:55
$begingroup$
As for converting the recurrence, he just substituted $i+3$ in place of $i$. Your second question confuses me. Do you understand what the $E$ operator does? $E^2 F_i-E F_i-F_i= F_i+2-F_i+1-F_i$ by definition of the operator. That this is identically $0$ is just the definition of the Fibonacci numbers.
$endgroup$
– saulspatz
Apr 1 at 1:55
$begingroup$
I'm clear as to what the $E$ operator does, I'm just confused as to how it is identical to 0.
$endgroup$
– Grayson
Apr 1 at 2:00
$begingroup$
I'm clear as to what the $E$ operator does, I'm just confused as to how it is identical to 0.
$endgroup$
– Grayson
Apr 1 at 2:00
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
For the Fibonacci numbers the recurrence identity is $F_n+2 = F_n+1 + F_n$. In the example the operator $E$ is such that $E f_n = f_n+1$. With this then
beginalign
F_n+2 &= F_n+1 + Fn \
E^2 F_n &= E F_n + F_n \
(E^2 - E -1) , F_n &= 0.
endalign
If $E^2 - E -1$ is considered as a polynomial then it can be found that:
$x^2 - x - 1 = 0$ with roots $ x = alpha, beta $ or
$$(E - alpha)(E - beta) F_n = 0.$$
In terms of the four term recurrence relation then:
beginalign
r_n+3 - 7 r_n+2 + 16 r_n+1 - 12 r_n &= 0 \
E^3 r_n - 7 E^2 r_n + 16 E r_n - 12 r_n &= 0 \
(E^3 - 7 E^2 + 16 E - 12) , r_n &= 0 \
(E - 3)(E - 2)^2 , r_n &= 0.
endalign
This demonstrates that $r_n$ has the form $r_n = 2^n , (a n + b) + c , 3^n$. Considering the initial conditions, $r_0 = 1, r_1 = 5, r_2 = 17$, then
$$r_n = 2^n , n + 3^n.$$
answered Apr 8 at 0:41
LeucippusLeucippus
19.8k102871
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3170107%2ffinding-annihilators-for-recurrence-relations%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
For the Fibonacci numbers the recurrence identity is $F_n+2 = F_n+1 + F_n$. In the example the operator $E$ is such that $E f_n = f_n+1$. With this then
beginalign
F_n+2 &= F_n+1 + Fn \
E^2 F_n &= E F_n + F_n \
(E^2 - E -1) , F_n &= 0.
endalign
If $E^2 - E -1$ is considered as a polynomial then it can be found that:
$x^2 - x - 1 = 0$ with roots $ x = alpha, beta $ or
$$(E - alpha)(E - beta) F_n = 0.$$
In terms of the four term recurrence relation then:
beginalign
r_n+3 - 7 r_n+2 + 16 r_n+1 - 12 r_n &= 0 \
E^3 r_n - 7 E^2 r_n + 16 E r_n - 12 r_n &= 0 \
(E^3 - 7 E^2 + 16 E - 12) , r_n &= 0 \
(E - 3)(E - 2)^2 , r_n &= 0.
endalign
This demonstrates that $r_n$ has the form $r_n = 2^n , (a n + b) + c , 3^n$. Considering the initial conditions, $r_0 = 1, r_1 = 5, r_2 = 17$, then
$$r_n = 2^n , n + 3^n.$$
answered Apr 8 at 0:41
LeucippusLeucippus
19.8k102871
$endgroup$
add a comment |
$begingroup$
For the Fibonacci numbers the recurrence identity is $F_n+2 = F_n+1 + F_n$. In the example the operator $E$ is such that $E f_n = f_n+1$. With this then
beginalign
F_n+2 &= F_n+1 + Fn \
E^2 F_n &= E F_n + F_n \
(E^2 - E -1) , F_n &= 0.
endalign
If $E^2 - E -1$ is considered as a polynomial then it can be found that:
$x^2 - x - 1 = 0$ with roots $ x = alpha, beta $ or
$$(E - alpha)(E - beta) F_n = 0.$$
In terms of the four term recurrence relation then:
beginalign
r_n+3 - 7 r_n+2 + 16 r_n+1 - 12 r_n &= 0 \
E^3 r_n - 7 E^2 r_n + 16 E r_n - 12 r_n &= 0 \
(E^3 - 7 E^2 + 16 E - 12) , r_n &= 0 \
(E - 3)(E - 2)^2 , r_n &= 0.
endalign
This demonstrates that $r_n$ has the form $r_n = 2^n , (a n + b) + c , 3^n$. Considering the initial conditions, $r_0 = 1, r_1 = 5, r_2 = 17$, then
$$r_n = 2^n , n + 3^n.$$
answered Apr 8 at 0:41
LeucippusLeucippus
19.8k102871
$endgroup$
add a comment |
$begingroup$
For the Fibonacci numbers the recurrence identity is $F_n+2 = F_n+1 + F_n$. In the example the operator $E$ is such that $E f_n = f_n+1$. With this then
beginalign
F_n+2 &= F_n+1 + Fn \
E^2 F_n &= E F_n + F_n \
(E^2 - E -1) , F_n &= 0.
endalign
If $E^2 - E -1$ is considered as a polynomial then it can be found that:
$x^2 - x - 1 = 0$ with roots $ x = alpha, beta $ or
$$(E - alpha)(E - beta) F_n = 0.$$
In terms of the four term recurrence relation then:
beginalign
r_n+3 - 7 r_n+2 + 16 r_n+1 - 12 r_n &= 0 \
E^3 r_n - 7 E^2 r_n + 16 E r_n - 12 r_n &= 0 \
(E^3 - 7 E^2 + 16 E - 12) , r_n &= 0 \
(E - 3)(E - 2)^2 , r_n &= 0.
endalign
This demonstrates that $r_n$ has the form $r_n = 2^n , (a n + b) + c , 3^n$. Considering the initial conditions, $r_0 = 1, r_1 = 5, r_2 = 17$, then
$$r_n = 2^n , n + 3^n.$$
answered Apr 8 at 0:41
LeucippusLeucippus
19.8k102871
$endgroup$
For the Fibonacci numbers the recurrence identity is $F_n+2 = F_n+1 + F_n$. In the example the operator $E$ is such that $E f_n = f_n+1$. With this then
beginalign
F_n+2 &= F_n+1 + Fn \
E^2 F_n &= E F_n + F_n \
(E^2 - E -1) , F_n &= 0.
endalign
If $E^2 - E -1$ is considered as a polynomial then it can be found that:
$x^2 - x - 1 = 0$ with roots $ x = alpha, beta $ or
$$(E - alpha)(E - beta) F_n = 0.$$
In terms of the four term recurrence relation then:
beginalign
r_n+3 - 7 r_n+2 + 16 r_n+1 - 12 r_n &= 0 \
E^3 r_n - 7 E^2 r_n + 16 E r_n - 12 r_n &= 0 \
(E^3 - 7 E^2 + 16 E - 12) , r_n &= 0 \
(E - 3)(E - 2)^2 , r_n &= 0.
endalign
This demonstrates that $r_n$ has the form $r_n = 2^n , (a n + b) + c , 3^n$. Considering the initial conditions, $r_0 = 1, r_1 = 5, r_2 = 17$, then
$$r_n = 2^n , n + 3^n.$$
answered Apr 8 at 0:41
LeucippusLeucippus
19.8k102871
answered Apr 8 at 0:41
LeucippusLeucippus
19.8k102871
answered Apr 8 at 0:41
LeucippusLeucippus
19.8k102871
answered Apr 8 at 0:41
LeucippusLeucippus
19.8k102871
19.8k102871
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3170107%2ffinding-annihilators-for-recurrence-relations%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
$begingroup$
Welcome to Math Stack Exchange. Replace $i$ with $i+3$
$endgroup$
– J. W. Tanner
Apr 1 at 1:52
$begingroup$
As for converting the recurrence, he just substituted $i+3$ in place of $i$. Your second question confuses me. Do you understand what the $E$ operator does? $E^2 F_i-E F_i-F_i= F_i+2-F_i+1-F_i$ by definition of the operator. That this is identically $0$ is just the definition of the Fibonacci numbers.
$endgroup$
– saulspatz
Apr 1 at 1:55
$begingroup$
I'm clear as to what the $E$ operator does, I'm just confused as to how it is identical to 0.
$endgroup$
– Grayson
Apr 1 at 2:00