Combinatorics: Finding a general solution for a recurrence relation. [closed]
$begingroup$
Find a general solution for this recurrence relation:
$$f(n) = 2f(n-1) + frac{(-1)^n}{n!}$$
when $f(0) = 0, f(1) = 1$
EDIT: n >= 2
combinatorics recurrence-relations generating-functions
asked Dec 30 '18 at 11:02
Robo YonuomaroRobo Yonuomaro
354
$endgroup$
closed as off-topic by Abcd, Martín Vacas Vignolo, A. Goodier, Paul Frost, José Carlos Santos Dec 30 '18 at 15:51
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Abcd, Martín Vacas Vignolo, A. Goodier, Paul Frost, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
add a comment |
$begingroup$
Find a general solution for this recurrence relation:
$$f(n) = 2f(n-1) + frac{(-1)^n}{n!}$$
when $f(0) = 0, f(1) = 1$
EDIT: n >= 2
combinatorics recurrence-relations generating-functions
asked Dec 30 '18 at 11:02
Robo YonuomaroRobo Yonuomaro
354
$endgroup$
closed as off-topic by Abcd, Martín Vacas Vignolo, A. Goodier, Paul Frost, José Carlos Santos Dec 30 '18 at 15:51
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Abcd, Martín Vacas Vignolo, A. Goodier, Paul Frost, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
What have you tried?
$endgroup$
– MisterRiemann
Dec 30 '18 at 11:04
$begingroup$
I have tried to use generating functions, but it just didn't go well...
$endgroup$
– Robo Yonuomaro
Dec 30 '18 at 11:07
$begingroup$
Iz is $$a_n=c_1 2^{n-1}+frac{2^n left(frac{Gamma left(n+1,-frac{1}{2}right)}{Gamma (n+1)}-sqrt{e}right)}{sqrt{e}}$$
$endgroup$
– Dr. Sonnhard Graubner
Dec 30 '18 at 11:12
$begingroup$
@Dr.SonnhardGraubner. This is pure magics !
$endgroup$
– Claude Leibovici
Dec 30 '18 at 14:25
$begingroup$
Expanding this into an answer would be appreciated.
$endgroup$
– marty cohen
Dec 30 '18 at 14:26
add a comment |
$begingroup$
Find a general solution for this recurrence relation:
$$f(n) = 2f(n-1) + frac{(-1)^n}{n!}$$
when $f(0) = 0, f(1) = 1$
EDIT: n >= 2
combinatorics recurrence-relations generating-functions
asked Dec 30 '18 at 11:02
Robo YonuomaroRobo Yonuomaro
354
$endgroup$
Find a general solution for this recurrence relation:
$$f(n) = 2f(n-1) + frac{(-1)^n}{n!}$$
when $f(0) = 0, f(1) = 1$
EDIT: n >= 2
combinatorics recurrence-relations generating-functions
combinatorics recurrence-relations generating-functions
asked Dec 30 '18 at 11:02
Robo YonuomaroRobo Yonuomaro
354
asked Dec 30 '18 at 11:02
Robo YonuomaroRobo Yonuomaro
354
edited Dec 30 '18 at 15:58
Robo Yonuomaro
asked Dec 30 '18 at 11:02
Robo YonuomaroRobo Yonuomaro
354
asked Dec 30 '18 at 11:02
Robo YonuomaroRobo Yonuomaro
354
asked Dec 30 '18 at 11:02
Robo YonuomaroRobo Yonuomaro
354
354
closed as off-topic by Abcd, Martín Vacas Vignolo, A. Goodier, Paul Frost, José Carlos Santos Dec 30 '18 at 15:51
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Abcd, Martín Vacas Vignolo, A. Goodier, Paul Frost, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
closed as off-topic by Abcd, Martín Vacas Vignolo, A. Goodier, Paul Frost, José Carlos Santos Dec 30 '18 at 15:51
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Abcd, Martín Vacas Vignolo, A. Goodier, Paul Frost, José Carlos Santos
If this question can be reworded to fit the rules in the help center, please edit the question.
$begingroup$
What have you tried?
$endgroup$
– MisterRiemann
Dec 30 '18 at 11:04
$begingroup$
I have tried to use generating functions, but it just didn't go well...
$endgroup$
– Robo Yonuomaro
Dec 30 '18 at 11:07
$begingroup$
Iz is $$a_n=c_1 2^{n-1}+frac{2^n left(frac{Gamma left(n+1,-frac{1}{2}right)}{Gamma (n+1)}-sqrt{e}right)}{sqrt{e}}$$
$endgroup$
– Dr. Sonnhard Graubner
Dec 30 '18 at 11:12
$begingroup$
@Dr.SonnhardGraubner. This is pure magics !
$endgroup$
– Claude Leibovici
Dec 30 '18 at 14:25
$begingroup$
Expanding this into an answer would be appreciated.
$endgroup$
– marty cohen
Dec 30 '18 at 14:26
add a comment |
$begingroup$
What have you tried?
$endgroup$
– MisterRiemann
Dec 30 '18 at 11:04
$begingroup$
I have tried to use generating functions, but it just didn't go well...
$endgroup$
– Robo Yonuomaro
Dec 30 '18 at 11:07
$begingroup$
Iz is $$a_n=c_1 2^{n-1}+frac{2^n left(frac{Gamma left(n+1,-frac{1}{2}right)}{Gamma (n+1)}-sqrt{e}right)}{sqrt{e}}$$
$endgroup$
– Dr. Sonnhard Graubner
Dec 30 '18 at 11:12
$begingroup$
@Dr.SonnhardGraubner. This is pure magics !
$endgroup$
– Claude Leibovici
Dec 30 '18 at 14:25
$begingroup$
Expanding this into an answer would be appreciated.
$endgroup$
– marty cohen
Dec 30 '18 at 14:26
$begingroup$
What have you tried?
$endgroup$
– MisterRiemann
Dec 30 '18 at 11:04
$begingroup$
What have you tried?
$endgroup$
– MisterRiemann
Dec 30 '18 at 11:04
$begingroup$
I have tried to use generating functions, but it just didn't go well...
$endgroup$
– Robo Yonuomaro
Dec 30 '18 at 11:07
$begingroup$
I have tried to use generating functions, but it just didn't go well...
$endgroup$
– Robo Yonuomaro
Dec 30 '18 at 11:07
$begingroup$
Iz is $$a_n=c_1 2^{n-1}+frac{2^n left(frac{Gamma left(n+1,-frac{1}{2}right)}{Gamma (n+1)}-sqrt{e}right)}{sqrt{e}}$$
$endgroup$
– Dr. Sonnhard Graubner
Dec 30 '18 at 11:12
$begingroup$
Iz is $$a_n=c_1 2^{n-1}+frac{2^n left(frac{Gamma left(n+1,-frac{1}{2}right)}{Gamma (n+1)}-sqrt{e}right)}{sqrt{e}}$$
$endgroup$
– Dr. Sonnhard Graubner
Dec 30 '18 at 11:12
$begingroup$
@Dr.SonnhardGraubner. This is pure magics !
$endgroup$
– Claude Leibovici
Dec 30 '18 at 14:25
$begingroup$
@Dr.SonnhardGraubner. This is pure magics !
$endgroup$
– Claude Leibovici
Dec 30 '18 at 14:25
$begingroup$
Expanding this into an answer would be appreciated.
$endgroup$
– marty cohen
Dec 30 '18 at 14:26
$begingroup$
Expanding this into an answer would be appreciated.
$endgroup$
– marty cohen
Dec 30 '18 at 14:26
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Remark: If $f(0)=0$, then $f(1)$ must be equal to $-1$, not $1$ as claimed. [Just plug $n=1$ in the recursion]
Multiply by $z^n$ and sum over $ngeq 1$
$$
sum_{ngeq 1}f(n)z^n=2sum_{ngeq 1}f(n-1)z^n+sum_{ngeq 1}frac{(-1)^n}{n!}z^n
$$
and define $sum_{ngeq 0}f(n)z^n=G(z)$. Hence
$$
G(z)-f(0)=2zG(z)-e^{-z} left(e^z-1right) .
$$
Using $f(0)=0$, this leads to
$$
G(z)=frac{ 1-e^{-z}}{2z-1} .
$$
The general term $f(n)$ of the recursion can be obtained from Cauchy's formula. Can you proceed from here?
answered Dec 30 '18 at 13:30
Pierpaolo VivoPierpaolo Vivo
5,3462724
$endgroup$
$begingroup$
You are right about that, I forgot to mention that n >= 2. How can it be solved with this?
$endgroup$
– Robo Yonuomaro
Dec 30 '18 at 15:57
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Remark: If $f(0)=0$, then $f(1)$ must be equal to $-1$, not $1$ as claimed. [Just plug $n=1$ in the recursion]
Multiply by $z^n$ and sum over $ngeq 1$
$$
sum_{ngeq 1}f(n)z^n=2sum_{ngeq 1}f(n-1)z^n+sum_{ngeq 1}frac{(-1)^n}{n!}z^n
$$
and define $sum_{ngeq 0}f(n)z^n=G(z)$. Hence
$$
G(z)-f(0)=2zG(z)-e^{-z} left(e^z-1right) .
$$
Using $f(0)=0$, this leads to
$$
G(z)=frac{ 1-e^{-z}}{2z-1} .
$$
The general term $f(n)$ of the recursion can be obtained from Cauchy's formula. Can you proceed from here?
answered Dec 30 '18 at 13:30
Pierpaolo VivoPierpaolo Vivo
5,3462724
$endgroup$
$begingroup$
You are right about that, I forgot to mention that n >= 2. How can it be solved with this?
$endgroup$
– Robo Yonuomaro
Dec 30 '18 at 15:57
add a comment |
$begingroup$
Remark: If $f(0)=0$, then $f(1)$ must be equal to $-1$, not $1$ as claimed. [Just plug $n=1$ in the recursion]
Multiply by $z^n$ and sum over $ngeq 1$
$$
sum_{ngeq 1}f(n)z^n=2sum_{ngeq 1}f(n-1)z^n+sum_{ngeq 1}frac{(-1)^n}{n!}z^n
$$
and define $sum_{ngeq 0}f(n)z^n=G(z)$. Hence
$$
G(z)-f(0)=2zG(z)-e^{-z} left(e^z-1right) .
$$
Using $f(0)=0$, this leads to
$$
G(z)=frac{ 1-e^{-z}}{2z-1} .
$$
The general term $f(n)$ of the recursion can be obtained from Cauchy's formula. Can you proceed from here?
answered Dec 30 '18 at 13:30
Pierpaolo VivoPierpaolo Vivo
5,3462724
$endgroup$
$begingroup$
You are right about that, I forgot to mention that n >= 2. How can it be solved with this?
$endgroup$
– Robo Yonuomaro
Dec 30 '18 at 15:57
add a comment |
$begingroup$
Remark: If $f(0)=0$, then $f(1)$ must be equal to $-1$, not $1$ as claimed. [Just plug $n=1$ in the recursion]
Multiply by $z^n$ and sum over $ngeq 1$
$$
sum_{ngeq 1}f(n)z^n=2sum_{ngeq 1}f(n-1)z^n+sum_{ngeq 1}frac{(-1)^n}{n!}z^n
$$
and define $sum_{ngeq 0}f(n)z^n=G(z)$. Hence
$$
G(z)-f(0)=2zG(z)-e^{-z} left(e^z-1right) .
$$
Using $f(0)=0$, this leads to
$$
G(z)=frac{ 1-e^{-z}}{2z-1} .
$$
The general term $f(n)$ of the recursion can be obtained from Cauchy's formula. Can you proceed from here?
answered Dec 30 '18 at 13:30
Pierpaolo VivoPierpaolo Vivo
5,3462724
$endgroup$
Remark: If $f(0)=0$, then $f(1)$ must be equal to $-1$, not $1$ as claimed. [Just plug $n=1$ in the recursion]
Multiply by $z^n$ and sum over $ngeq 1$
$$
sum_{ngeq 1}f(n)z^n=2sum_{ngeq 1}f(n-1)z^n+sum_{ngeq 1}frac{(-1)^n}{n!}z^n
$$
and define $sum_{ngeq 0}f(n)z^n=G(z)$. Hence
$$
G(z)-f(0)=2zG(z)-e^{-z} left(e^z-1right) .
$$
Using $f(0)=0$, this leads to
$$
G(z)=frac{ 1-e^{-z}}{2z-1} .
$$
The general term $f(n)$ of the recursion can be obtained from Cauchy's formula. Can you proceed from here?
answered Dec 30 '18 at 13:30
Pierpaolo VivoPierpaolo Vivo
5,3462724
answered Dec 30 '18 at 13:30
Pierpaolo VivoPierpaolo Vivo
5,3462724
answered Dec 30 '18 at 13:30
Pierpaolo VivoPierpaolo Vivo
5,3462724
answered Dec 30 '18 at 13:30
Pierpaolo VivoPierpaolo Vivo
5,3462724
5,3462724
$begingroup$
You are right about that, I forgot to mention that n >= 2. How can it be solved with this?
$endgroup$
– Robo Yonuomaro
Dec 30 '18 at 15:57
add a comment |
$begingroup$
You are right about that, I forgot to mention that n >= 2. How can it be solved with this?
$endgroup$
– Robo Yonuomaro
Dec 30 '18 at 15:57
$begingroup$
You are right about that, I forgot to mention that n >= 2. How can it be solved with this?
$endgroup$
– Robo Yonuomaro
Dec 30 '18 at 15:57
$begingroup$
You are right about that, I forgot to mention that n >= 2. How can it be solved with this?
$endgroup$
– Robo Yonuomaro
Dec 30 '18 at 15:57
add a comment |
$begingroup$
What have you tried?
$endgroup$
– MisterRiemann
Dec 30 '18 at 11:04
$begingroup$
I have tried to use generating functions, but it just didn't go well...
$endgroup$
– Robo Yonuomaro
Dec 30 '18 at 11:07
$begingroup$
Iz is $$a_n=c_1 2^{n-1}+frac{2^n left(frac{Gamma left(n+1,-frac{1}{2}right)}{Gamma (n+1)}-sqrt{e}right)}{sqrt{e}}$$
$endgroup$
– Dr. Sonnhard Graubner
Dec 30 '18 at 11:12
$begingroup$
@Dr.SonnhardGraubner. This is pure magics !
$endgroup$
– Claude Leibovici
Dec 30 '18 at 14:25
$begingroup$
Expanding this into an answer would be appreciated.
$endgroup$
– marty cohen
Dec 30 '18 at 14:26