Formula for $a_n$ where $a_n$ = n*($a_{n-1}$+$a_{n-2}$)
$begingroup$
Formula for $a_n$ if $a_0=1$ and $a_1=2$ and n greater than equal to 2
$a_n$ = $n times (a_{n-1}+a_{n-2}$).
Attempt: $ a_2 =6, a_3=24, a_4=120, a_5=720 , a_6 = 5040 $ It so looks like $a_n= (n+1)!$
I tried to open $n times (n-1 times (a_{n-2}+a_{n-3}) + a_{n-2}$).
Unable to get formula in factorial terms.
sequences-and-series combinatorics discrete-mathematics recurrence-relations
$endgroup$
add a comment |
$begingroup$
Formula for $a_n$ if $a_0=1$ and $a_1=2$ and n greater than equal to 2
$a_n$ = $n times (a_{n-1}+a_{n-2}$).
Attempt: $ a_2 =6, a_3=24, a_4=120, a_5=720 , a_6 = 5040 $ It so looks like $a_n= (n+1)!$
I tried to open $n times (n-1 times (a_{n-2}+a_{n-3}) + a_{n-2}$).
Unable to get formula in factorial terms.
sequences-and-series combinatorics discrete-mathematics recurrence-relations
$endgroup$
$begingroup$
Hint: Have you tried using induction?
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:15
$begingroup$
Using induction seems like cheating. I was thinking more in terms of generating functions, once unable to do directly by splitting.
$endgroup$
– Amrita
Sep 19 '16 at 4:34
1
$begingroup$
Another way to look at it is that all you know about the sequence $a_n$ is an inductive definition, so you have to use induction to prove anything about it. The use of induction might be implicit, but it's there somewhere. (If you wrote down all the formal details of a proof using generating functions, you'd have to use induction; if your proof uses $"ldots"$ anywhere, a formal proof would use induction; etc.)
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:39
$begingroup$
Wow! thanks, didn't know that. Always thought generating functions was the superior way to do recurrence relations.
$endgroup$
– Amrita
Sep 19 '16 at 4:46
1
$begingroup$
Generating functions are fine, and they can be a great way to discover and organize a proof. But fundamentally they aren't an alternative to induction; they're really a way to handle the bookkeeping of an induction automatically (and also to connect things with concepts of analysis, which can be useful). So I certainly don't mean to discourage the use of generating functions!
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:48
add a comment |
$begingroup$
Formula for $a_n$ if $a_0=1$ and $a_1=2$ and n greater than equal to 2
$a_n$ = $n times (a_{n-1}+a_{n-2}$).
Attempt: $ a_2 =6, a_3=24, a_4=120, a_5=720 , a_6 = 5040 $ It so looks like $a_n= (n+1)!$
I tried to open $n times (n-1 times (a_{n-2}+a_{n-3}) + a_{n-2}$).
Unable to get formula in factorial terms.
sequences-and-series combinatorics discrete-mathematics recurrence-relations
$endgroup$
Formula for $a_n$ if $a_0=1$ and $a_1=2$ and n greater than equal to 2
$a_n$ = $n times (a_{n-1}+a_{n-2}$).
Attempt: $ a_2 =6, a_3=24, a_4=120, a_5=720 , a_6 = 5040 $ It so looks like $a_n= (n+1)!$
I tried to open $n times (n-1 times (a_{n-2}+a_{n-3}) + a_{n-2}$).
Unable to get formula in factorial terms.
sequences-and-series combinatorics discrete-mathematics recurrence-relations
sequences-and-series combinatorics discrete-mathematics recurrence-relations
asked Sep 19 '16 at 4:09
AmritaAmrita
435314
435314
$begingroup$
Hint: Have you tried using induction?
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:15
$begingroup$
Using induction seems like cheating. I was thinking more in terms of generating functions, once unable to do directly by splitting.
$endgroup$
– Amrita
Sep 19 '16 at 4:34
1
$begingroup$
Another way to look at it is that all you know about the sequence $a_n$ is an inductive definition, so you have to use induction to prove anything about it. The use of induction might be implicit, but it's there somewhere. (If you wrote down all the formal details of a proof using generating functions, you'd have to use induction; if your proof uses $"ldots"$ anywhere, a formal proof would use induction; etc.)
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:39
$begingroup$
Wow! thanks, didn't know that. Always thought generating functions was the superior way to do recurrence relations.
$endgroup$
– Amrita
Sep 19 '16 at 4:46
1
$begingroup$
Generating functions are fine, and they can be a great way to discover and organize a proof. But fundamentally they aren't an alternative to induction; they're really a way to handle the bookkeeping of an induction automatically (and also to connect things with concepts of analysis, which can be useful). So I certainly don't mean to discourage the use of generating functions!
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:48
add a comment |
$begingroup$
Hint: Have you tried using induction?
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:15
$begingroup$
Using induction seems like cheating. I was thinking more in terms of generating functions, once unable to do directly by splitting.
$endgroup$
– Amrita
Sep 19 '16 at 4:34
1
$begingroup$
Another way to look at it is that all you know about the sequence $a_n$ is an inductive definition, so you have to use induction to prove anything about it. The use of induction might be implicit, but it's there somewhere. (If you wrote down all the formal details of a proof using generating functions, you'd have to use induction; if your proof uses $"ldots"$ anywhere, a formal proof would use induction; etc.)
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:39
$begingroup$
Wow! thanks, didn't know that. Always thought generating functions was the superior way to do recurrence relations.
$endgroup$
– Amrita
Sep 19 '16 at 4:46
1
$begingroup$
Generating functions are fine, and they can be a great way to discover and organize a proof. But fundamentally they aren't an alternative to induction; they're really a way to handle the bookkeeping of an induction automatically (and also to connect things with concepts of analysis, which can be useful). So I certainly don't mean to discourage the use of generating functions!
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:48
$begingroup$
Hint: Have you tried using induction?
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:15
$begingroup$
Hint: Have you tried using induction?
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:15
$begingroup$
Using induction seems like cheating. I was thinking more in terms of generating functions, once unable to do directly by splitting.
$endgroup$
– Amrita
Sep 19 '16 at 4:34
$begingroup$
Using induction seems like cheating. I was thinking more in terms of generating functions, once unable to do directly by splitting.
$endgroup$
– Amrita
Sep 19 '16 at 4:34
1
1
$begingroup$
Another way to look at it is that all you know about the sequence $a_n$ is an inductive definition, so you have to use induction to prove anything about it. The use of induction might be implicit, but it's there somewhere. (If you wrote down all the formal details of a proof using generating functions, you'd have to use induction; if your proof uses $"ldots"$ anywhere, a formal proof would use induction; etc.)
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:39
$begingroup$
Another way to look at it is that all you know about the sequence $a_n$ is an inductive definition, so you have to use induction to prove anything about it. The use of induction might be implicit, but it's there somewhere. (If you wrote down all the formal details of a proof using generating functions, you'd have to use induction; if your proof uses $"ldots"$ anywhere, a formal proof would use induction; etc.)
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:39
$begingroup$
Wow! thanks, didn't know that. Always thought generating functions was the superior way to do recurrence relations.
$endgroup$
– Amrita
Sep 19 '16 at 4:46
$begingroup$
Wow! thanks, didn't know that. Always thought generating functions was the superior way to do recurrence relations.
$endgroup$
– Amrita
Sep 19 '16 at 4:46
1
1
$begingroup$
Generating functions are fine, and they can be a great way to discover and organize a proof. But fundamentally they aren't an alternative to induction; they're really a way to handle the bookkeeping of an induction automatically (and also to connect things with concepts of analysis, which can be useful). So I certainly don't mean to discourage the use of generating functions!
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:48
$begingroup$
Generating functions are fine, and they can be a great way to discover and organize a proof. But fundamentally they aren't an alternative to induction; they're really a way to handle the bookkeeping of an induction automatically (and also to connect things with concepts of analysis, which can be useful). So I certainly don't mean to discourage the use of generating functions!
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:48
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Once you've noticed the pattern, it can be proved using induction on $n$:
For the base case, $a_0=1!$, $a_1=2!$.
For the induction step, if $n>1$ and $a_k=(k+1)!$ for $0leq kleq n-1$, then
$$ a_n=n(a_{n-1}+a_{n-2})=n(n!+(n-1)!)=n(n-1)!(n+1)=(n+1)!$$
$endgroup$
$begingroup$
I was thinking in terms of generating functions. For me multiplying by $x^n$ both sides to get g.f seems to not work. Any way I can do this using generating functions. I am trying to learn g.f
$endgroup$
– Amrita
Sep 19 '16 at 4:36
$begingroup$
Maybe try an exponential generating function instead? I think induction is the simplest approach.
$endgroup$
– carmichael561
Sep 19 '16 at 4:42
add a comment |
$begingroup$
There is a way to solve this using generating functions. The use of ordinary generating functions is more complicated due to convergence failure, but exponential generating functions work in this case.
Suppose $,a_n,$ is a sequence of numbers. Then $,y =E[a_n] := sum_{n=0}^infty a_n x^n/n!,$ is its exponential generating function. The two properties we need are $, E[na_n] = xy',$ and $,E[a_{n+1}] = y'.,$ The recursion is $,a_n = n times (a_{n-1}+a_{n-2}).,$
We modify the recursion to be $,a_{n+2} = (n+2)(a_{n+1} + a_n).,$ Now $E[a_{n+2}] = y'',,$
$,E[a_{n+1}+a_n] = (y+y').,$ The recursion becomes
$$ y'' = 2(y+y') + x(y+y')' = 2y + (x+2)y' + xy''. $$
Solving this differential equation with the initial conditions $,y(0) = 1,, y'(0) = 2,$ gives the solution $, y(x) = 1/(1-x)^2.,$ Now $, y = 1 + 2x + 3x^2 + cdots = sum_{n=0}^infty (n+1)x^n $ and thus $,y = E[(n+1)n!],$ or simply $,a_n = (n+1)!.$
$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%2f1932388%2fformula-for-a-n-where-a-n-na-n-1a-n-2%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Once you've noticed the pattern, it can be proved using induction on $n$:
For the base case, $a_0=1!$, $a_1=2!$.
For the induction step, if $n>1$ and $a_k=(k+1)!$ for $0leq kleq n-1$, then
$$ a_n=n(a_{n-1}+a_{n-2})=n(n!+(n-1)!)=n(n-1)!(n+1)=(n+1)!$$
$endgroup$
$begingroup$
I was thinking in terms of generating functions. For me multiplying by $x^n$ both sides to get g.f seems to not work. Any way I can do this using generating functions. I am trying to learn g.f
$endgroup$
– Amrita
Sep 19 '16 at 4:36
$begingroup$
Maybe try an exponential generating function instead? I think induction is the simplest approach.
$endgroup$
– carmichael561
Sep 19 '16 at 4:42
add a comment |
$begingroup$
Once you've noticed the pattern, it can be proved using induction on $n$:
For the base case, $a_0=1!$, $a_1=2!$.
For the induction step, if $n>1$ and $a_k=(k+1)!$ for $0leq kleq n-1$, then
$$ a_n=n(a_{n-1}+a_{n-2})=n(n!+(n-1)!)=n(n-1)!(n+1)=(n+1)!$$
$endgroup$
$begingroup$
I was thinking in terms of generating functions. For me multiplying by $x^n$ both sides to get g.f seems to not work. Any way I can do this using generating functions. I am trying to learn g.f
$endgroup$
– Amrita
Sep 19 '16 at 4:36
$begingroup$
Maybe try an exponential generating function instead? I think induction is the simplest approach.
$endgroup$
– carmichael561
Sep 19 '16 at 4:42
add a comment |
$begingroup$
Once you've noticed the pattern, it can be proved using induction on $n$:
For the base case, $a_0=1!$, $a_1=2!$.
For the induction step, if $n>1$ and $a_k=(k+1)!$ for $0leq kleq n-1$, then
$$ a_n=n(a_{n-1}+a_{n-2})=n(n!+(n-1)!)=n(n-1)!(n+1)=(n+1)!$$
$endgroup$
Once you've noticed the pattern, it can be proved using induction on $n$:
For the base case, $a_0=1!$, $a_1=2!$.
For the induction step, if $n>1$ and $a_k=(k+1)!$ for $0leq kleq n-1$, then
$$ a_n=n(a_{n-1}+a_{n-2})=n(n!+(n-1)!)=n(n-1)!(n+1)=(n+1)!$$
answered Sep 19 '16 at 4:16
carmichael561carmichael561
47.1k54583
47.1k54583
$begingroup$
I was thinking in terms of generating functions. For me multiplying by $x^n$ both sides to get g.f seems to not work. Any way I can do this using generating functions. I am trying to learn g.f
$endgroup$
– Amrita
Sep 19 '16 at 4:36
$begingroup$
Maybe try an exponential generating function instead? I think induction is the simplest approach.
$endgroup$
– carmichael561
Sep 19 '16 at 4:42
add a comment |
$begingroup$
I was thinking in terms of generating functions. For me multiplying by $x^n$ both sides to get g.f seems to not work. Any way I can do this using generating functions. I am trying to learn g.f
$endgroup$
– Amrita
Sep 19 '16 at 4:36
$begingroup$
Maybe try an exponential generating function instead? I think induction is the simplest approach.
$endgroup$
– carmichael561
Sep 19 '16 at 4:42
$begingroup$
I was thinking in terms of generating functions. For me multiplying by $x^n$ both sides to get g.f seems to not work. Any way I can do this using generating functions. I am trying to learn g.f
$endgroup$
– Amrita
Sep 19 '16 at 4:36
$begingroup$
I was thinking in terms of generating functions. For me multiplying by $x^n$ both sides to get g.f seems to not work. Any way I can do this using generating functions. I am trying to learn g.f
$endgroup$
– Amrita
Sep 19 '16 at 4:36
$begingroup$
Maybe try an exponential generating function instead? I think induction is the simplest approach.
$endgroup$
– carmichael561
Sep 19 '16 at 4:42
$begingroup$
Maybe try an exponential generating function instead? I think induction is the simplest approach.
$endgroup$
– carmichael561
Sep 19 '16 at 4:42
add a comment |
$begingroup$
There is a way to solve this using generating functions. The use of ordinary generating functions is more complicated due to convergence failure, but exponential generating functions work in this case.
Suppose $,a_n,$ is a sequence of numbers. Then $,y =E[a_n] := sum_{n=0}^infty a_n x^n/n!,$ is its exponential generating function. The two properties we need are $, E[na_n] = xy',$ and $,E[a_{n+1}] = y'.,$ The recursion is $,a_n = n times (a_{n-1}+a_{n-2}).,$
We modify the recursion to be $,a_{n+2} = (n+2)(a_{n+1} + a_n).,$ Now $E[a_{n+2}] = y'',,$
$,E[a_{n+1}+a_n] = (y+y').,$ The recursion becomes
$$ y'' = 2(y+y') + x(y+y')' = 2y + (x+2)y' + xy''. $$
Solving this differential equation with the initial conditions $,y(0) = 1,, y'(0) = 2,$ gives the solution $, y(x) = 1/(1-x)^2.,$ Now $, y = 1 + 2x + 3x^2 + cdots = sum_{n=0}^infty (n+1)x^n $ and thus $,y = E[(n+1)n!],$ or simply $,a_n = (n+1)!.$
$endgroup$
add a comment |
$begingroup$
There is a way to solve this using generating functions. The use of ordinary generating functions is more complicated due to convergence failure, but exponential generating functions work in this case.
Suppose $,a_n,$ is a sequence of numbers. Then $,y =E[a_n] := sum_{n=0}^infty a_n x^n/n!,$ is its exponential generating function. The two properties we need are $, E[na_n] = xy',$ and $,E[a_{n+1}] = y'.,$ The recursion is $,a_n = n times (a_{n-1}+a_{n-2}).,$
We modify the recursion to be $,a_{n+2} = (n+2)(a_{n+1} + a_n).,$ Now $E[a_{n+2}] = y'',,$
$,E[a_{n+1}+a_n] = (y+y').,$ The recursion becomes
$$ y'' = 2(y+y') + x(y+y')' = 2y + (x+2)y' + xy''. $$
Solving this differential equation with the initial conditions $,y(0) = 1,, y'(0) = 2,$ gives the solution $, y(x) = 1/(1-x)^2.,$ Now $, y = 1 + 2x + 3x^2 + cdots = sum_{n=0}^infty (n+1)x^n $ and thus $,y = E[(n+1)n!],$ or simply $,a_n = (n+1)!.$
$endgroup$
add a comment |
$begingroup$
There is a way to solve this using generating functions. The use of ordinary generating functions is more complicated due to convergence failure, but exponential generating functions work in this case.
Suppose $,a_n,$ is a sequence of numbers. Then $,y =E[a_n] := sum_{n=0}^infty a_n x^n/n!,$ is its exponential generating function. The two properties we need are $, E[na_n] = xy',$ and $,E[a_{n+1}] = y'.,$ The recursion is $,a_n = n times (a_{n-1}+a_{n-2}).,$
We modify the recursion to be $,a_{n+2} = (n+2)(a_{n+1} + a_n).,$ Now $E[a_{n+2}] = y'',,$
$,E[a_{n+1}+a_n] = (y+y').,$ The recursion becomes
$$ y'' = 2(y+y') + x(y+y')' = 2y + (x+2)y' + xy''. $$
Solving this differential equation with the initial conditions $,y(0) = 1,, y'(0) = 2,$ gives the solution $, y(x) = 1/(1-x)^2.,$ Now $, y = 1 + 2x + 3x^2 + cdots = sum_{n=0}^infty (n+1)x^n $ and thus $,y = E[(n+1)n!],$ or simply $,a_n = (n+1)!.$
$endgroup$
There is a way to solve this using generating functions. The use of ordinary generating functions is more complicated due to convergence failure, but exponential generating functions work in this case.
Suppose $,a_n,$ is a sequence of numbers. Then $,y =E[a_n] := sum_{n=0}^infty a_n x^n/n!,$ is its exponential generating function. The two properties we need are $, E[na_n] = xy',$ and $,E[a_{n+1}] = y'.,$ The recursion is $,a_n = n times (a_{n-1}+a_{n-2}).,$
We modify the recursion to be $,a_{n+2} = (n+2)(a_{n+1} + a_n).,$ Now $E[a_{n+2}] = y'',,$
$,E[a_{n+1}+a_n] = (y+y').,$ The recursion becomes
$$ y'' = 2(y+y') + x(y+y')' = 2y + (x+2)y' + xy''. $$
Solving this differential equation with the initial conditions $,y(0) = 1,, y'(0) = 2,$ gives the solution $, y(x) = 1/(1-x)^2.,$ Now $, y = 1 + 2x + 3x^2 + cdots = sum_{n=0}^infty (n+1)x^n $ and thus $,y = E[(n+1)n!],$ or simply $,a_n = (n+1)!.$
answered Dec 23 '18 at 16:21
SomosSomos
14.5k11336
14.5k11336
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%2f1932388%2fformula-for-a-n-where-a-n-na-n-1a-n-2%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$
Hint: Have you tried using induction?
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:15
$begingroup$
Using induction seems like cheating. I was thinking more in terms of generating functions, once unable to do directly by splitting.
$endgroup$
– Amrita
Sep 19 '16 at 4:34
1
$begingroup$
Another way to look at it is that all you know about the sequence $a_n$ is an inductive definition, so you have to use induction to prove anything about it. The use of induction might be implicit, but it's there somewhere. (If you wrote down all the formal details of a proof using generating functions, you'd have to use induction; if your proof uses $"ldots"$ anywhere, a formal proof would use induction; etc.)
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:39
$begingroup$
Wow! thanks, didn't know that. Always thought generating functions was the superior way to do recurrence relations.
$endgroup$
– Amrita
Sep 19 '16 at 4:46
1
$begingroup$
Generating functions are fine, and they can be a great way to discover and organize a proof. But fundamentally they aren't an alternative to induction; they're really a way to handle the bookkeeping of an induction automatically (and also to connect things with concepts of analysis, which can be useful). So I certainly don't mean to discourage the use of generating functions!
$endgroup$
– Mitchell Spector
Sep 19 '16 at 4:48