Fdtxjr

Do I have a twin with permutated remainders?

RSA: Danger of using p to create q

What would happen to a modern skyscraper if it rains micro blackholes?

Unable to deploy metadata from Partner Developer scratch org because of extra fields

Is it possible to run Internet Explorer on OS X El Capitan?

Perform and show arithmetic with LuaLaTeX

Client team has low performances and low technical skills: we always fix their work and now they stop collaborate with us. How to solve?

How do I deal with an unproductive colleague in a small company?

Accidentally leaked the solution to an assignment, what to do now? (I'm the prof)

What does it mean to describe someone as a butt steak?

What are these boxed doors outside store fronts in New York?

Why can't I see bouncing of switch on oscilloscope screen?

Could an aircraft fly or hover using only jets of compressed air?

If human space travel is limited by the G force vulnerability, is there a way to counter G forces?

Why is 150k or 200k jobs considered good when there's 300k+ births a month?

Does detail obscure or enhance action?

Can a vampire attack twice with their claws using Multiattack?

How to determine what difficulty is right for the game?

How is the claim "I am in New York only if I am in America" the same as "If I am in New York, then I am in America?

Important Resources for Dark Age Civilizations?

Can I ask the recruiters in my resume to put the reason why I am rejected?

Which country benefited the most from UN Security Council vetoes?

Revoked SSL certificate

I'm flying to France today and my passport expires in less than 2 months

Recursion Question using Generating Functions

Recurrence relations and generating functions questionTextbook questions on generating functionsQuestion about generating functions with trigRecurrence relation to closed form of generating functionDerive a closed formula for the generating function of this recurrence relationSolving a recurrence relation using generating functionsUse generating functions to solve $a_n = 6a_n-1 - 8a_n-2 + 3 $ and…Solving the recurrence $a_n+2 = 3a_n+1 - 2a_n, a_0 = 1, a_1 = 3$ using generating functionsSolving $a_n+1 = c_n a_n$ using generating functionsHow to find the generating function of one recurrence relation in terms of that of another

1

$begingroup$

Here is my question:

Consider the recurrence,
$$a_n+1=2a_n+(-1)^n$$
with initial condition,
$$a_0=0$$

Find and prove a formula for $a_n$.

I don't really know how to prove this formula

I tried going with a generating function method, but that kind of led nowhere.

sequences-and-series discrete-mathematics recurrence-relations generating-functions

share|cite|improve this question

edited Mar 21 at 18:11

Martin Hansen

780114

asked Mar 21 at 0:28

Michael MaoMichael Mao

161

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Have you learnt about how to solve recurrences like $a_n+1=2a_n+(-1)^n$?
  $endgroup$
  – Minus One-Twelfth
  Mar 21 at 0:30
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I got something like 1 / (1-2x)(1+x) but that seems nowhere near what I want
  $endgroup$
  – Michael Mao
  Mar 21 at 0:31
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Please do not use image for the critical part of the question. Click on the tiny edit and use MathJax to properly typeset math expressions.
  $endgroup$
  – Lee David Chung Lin
  Mar 21 at 1:02
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I've copied the significant parts of the question into MathJax, and added a full answer below. Hope that helps !
  $endgroup$
  – Martin Hansen
  Mar 21 at 18:16
  

  
  
  
  

add a comment | 

1

$begingroup$

Here is my question:

Consider the recurrence,
$$a_n+1=2a_n+(-1)^n$$
with initial condition,
$$a_0=0$$

Find and prove a formula for $a_n$.

I don't really know how to prove this formula

I tried going with a generating function method, but that kind of led nowhere.

sequences-and-series discrete-mathematics recurrence-relations generating-functions

share|cite|improve this question

edited Mar 21 at 18:11

Martin Hansen

780114

asked Mar 21 at 0:28

Michael MaoMichael Mao

161

$endgroup$

• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Have you learnt about how to solve recurrences like $a_n+1=2a_n+(-1)^n$?
  $endgroup$
  – Minus One-Twelfth
  Mar 21 at 0:30
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I got something like 1 / (1-2x)(1+x) but that seems nowhere near what I want
  $endgroup$
  – Michael Mao
  Mar 21 at 0:31
  

  
  
  
  


• 
  
  
  

  
  2
  

  
  
  
  
  
  

  
  $begingroup$
  Please do not use image for the critical part of the question. Click on the tiny edit and use MathJax to properly typeset math expressions.
  $endgroup$
  – Lee David Chung Lin
  Mar 21 at 1:02
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  I've copied the significant parts of the question into MathJax, and added a full answer below. Hope that helps !
  $endgroup$
  – Martin Hansen
  Mar 21 at 18:16
  

  
  
  
  

add a comment | 

$begingroup$

Here is my question:

Consider the recurrence,
$$a_n+1=2a_n+(-1)^n$$
with initial condition,
$$a_0=0$$

Find and prove a formula for $a_n$.

I don't really know how to prove this formula

I tried going with a generating function method, but that kind of led nowhere.

sequences-and-series discrete-mathematics recurrence-relations generating-functions

share|cite|improve this question

edited Mar 21 at 18:11

Martin Hansen

780114

asked Mar 21 at 0:28

Michael MaoMichael Mao

161

$endgroup$

share|cite|improve this question

edited Mar 21 at 18:11

Martin Hansen

780114

asked Mar 21 at 0:28

Michael MaoMichael Mao

161

share|cite|improve this question

edited Mar 21 at 18:11

Martin Hansen

780114

asked Mar 21 at 0:28

Michael MaoMichael Mao

161

edited Mar 21 at 18:11

Martin Hansen

780114

edited Mar 21 at 18:11

Martin Hansen

780114

asked Mar 21 at 0:28

Michael MaoMichael Mao

161

asked Mar 21 at 0:28

Michael MaoMichael Mao

161

2 Answers
2

active

oldest

votes

0

$begingroup$

The sequence generated by the recurrence relation is;
$$0, 1, 1, 3, 5, 11, 21, dots$$
Write the recurrence relation as;
$$a_n-2a_n-1=(-1)(-1)^n$$
Get the generating function, $GF$ in the standard way;
$$GF=0+x+x^2+3x^3+5x^4+11x^5+21x^6+dots$$
$$-2xGF=0+0x-2x^2-2x^3-6x^4-10x^5-22x^6+dots$$
$$(1-2x)GF=0+x-x^2+x^3-x^4+x^5-x^6+x^7-x^8+ dots$$
$$(1-2x)GF=-big(frac11+xbig)+1$$
$$GF=fracx(1-2x)(1+x)$$
Use partial fractions to get;
$$GF=frac13times frac11-2x-frac13times frac11+x$$
These are standard bits that translate directly into the formula;
$$a_n=frac132^n-frac13(-1)^n$$
or
$$a_n=frac2^n-(-1)^n3$$
Check this gives the sequence expected, which it does!

share|cite|improve this answer

answered Mar 21 at 17:28

Martin HansenMartin Hansen

780114

$endgroup$

add a comment | 

0

$begingroup$

Hint.

Calling

$$
G(x) = sum_k=0^inftya_k x^k
$$

we have

$$
a_k+1x^k-2a_k x^k -(-1)^k x^k = 0
$$

or

$$
frac 1xsum_k=1^inftya_k x^k - 2sum_k=0^inftya_k x^k-sum_k=0^infty(-1)^k x^k = 0
$$

now assuming $|x| < 1$ we have

$$
frac 1x (G(x)-a_0)-2G(x)-frac1x+1=0
$$

and

$$
G(x) = fraca_01-2x+frac 13frac11-2x-frac 13frac11+x
$$

etc.

share|cite|improve this answer

answered Mar 21 at 22:48

CesareoCesareo

9,7263517

$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
);



);

draft saved

draft discarded

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

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3156168%2frecursion-question-using-generating-functions%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

0

$begingroup$

The sequence generated by the recurrence relation is;
$$0, 1, 1, 3, 5, 11, 21, dots$$
Write the recurrence relation as;
$$a_n-2a_n-1=(-1)(-1)^n$$
Get the generating function, $GF$ in the standard way;
$$GF=0+x+x^2+3x^3+5x^4+11x^5+21x^6+dots$$
$$-2xGF=0+0x-2x^2-2x^3-6x^4-10x^5-22x^6+dots$$
$$(1-2x)GF=0+x-x^2+x^3-x^4+x^5-x^6+x^7-x^8+ dots$$
$$(1-2x)GF=-big(frac11+xbig)+1$$
$$GF=fracx(1-2x)(1+x)$$
Use partial fractions to get;
$$GF=frac13times frac11-2x-frac13times frac11+x$$
These are standard bits that translate directly into the formula;
$$a_n=frac132^n-frac13(-1)^n$$
or
$$a_n=frac2^n-(-1)^n3$$
Check this gives the sequence expected, which it does!

share|cite|improve this answer

answered Mar 21 at 17:28

Martin HansenMartin Hansen

780114

$endgroup$

add a comment | 

0

$begingroup$

The sequence generated by the recurrence relation is;
$$0, 1, 1, 3, 5, 11, 21, dots$$
Write the recurrence relation as;
$$a_n-2a_n-1=(-1)(-1)^n$$
Get the generating function, $GF$ in the standard way;
$$GF=0+x+x^2+3x^3+5x^4+11x^5+21x^6+dots$$
$$-2xGF=0+0x-2x^2-2x^3-6x^4-10x^5-22x^6+dots$$
$$(1-2x)GF=0+x-x^2+x^3-x^4+x^5-x^6+x^7-x^8+ dots$$
$$(1-2x)GF=-big(frac11+xbig)+1$$
$$GF=fracx(1-2x)(1+x)$$
Use partial fractions to get;
$$GF=frac13times frac11-2x-frac13times frac11+x$$
These are standard bits that translate directly into the formula;
$$a_n=frac132^n-frac13(-1)^n$$
or
$$a_n=frac2^n-(-1)^n3$$
Check this gives the sequence expected, which it does!

share|cite|improve this answer

answered Mar 21 at 17:28

Martin HansenMartin Hansen

780114

$endgroup$

add a comment | 

$begingroup$

The sequence generated by the recurrence relation is;
$$0, 1, 1, 3, 5, 11, 21, dots$$
Write the recurrence relation as;
$$a_n-2a_n-1=(-1)(-1)^n$$
Get the generating function, $GF$ in the standard way;
$$GF=0+x+x^2+3x^3+5x^4+11x^5+21x^6+dots$$
$$-2xGF=0+0x-2x^2-2x^3-6x^4-10x^5-22x^6+dots$$
$$(1-2x)GF=0+x-x^2+x^3-x^4+x^5-x^6+x^7-x^8+ dots$$
$$(1-2x)GF=-big(frac11+xbig)+1$$
$$GF=fracx(1-2x)(1+x)$$
Use partial fractions to get;
$$GF=frac13times frac11-2x-frac13times frac11+x$$
These are standard bits that translate directly into the formula;
$$a_n=frac132^n-frac13(-1)^n$$
or
$$a_n=frac2^n-(-1)^n3$$
Check this gives the sequence expected, which it does!

share|cite|improve this answer

answered Mar 21 at 17:28

Martin HansenMartin Hansen

780114

$endgroup$

share|cite|improve this answer

answered Mar 21 at 17:28

Martin HansenMartin Hansen

780114

answered Mar 21 at 17:28

Martin HansenMartin Hansen

780114

answered Mar 21 at 17:28

Martin HansenMartin Hansen

780114

0

$begingroup$

Hint.

Calling

$$
G(x) = sum_k=0^inftya_k x^k
$$

we have

$$
a_k+1x^k-2a_k x^k -(-1)^k x^k = 0
$$

or

$$
frac 1xsum_k=1^inftya_k x^k - 2sum_k=0^inftya_k x^k-sum_k=0^infty(-1)^k x^k = 0
$$

now assuming $|x| < 1$ we have

$$
frac 1x (G(x)-a_0)-2G(x)-frac1x+1=0
$$

and

$$
G(x) = fraca_01-2x+frac 13frac11-2x-frac 13frac11+x
$$

etc.

share|cite|improve this answer

answered Mar 21 at 22:48

CesareoCesareo

9,7263517

$endgroup$

add a comment | 

0

$begingroup$

Hint.

Calling

$$
G(x) = sum_k=0^inftya_k x^k
$$

we have

$$
a_k+1x^k-2a_k x^k -(-1)^k x^k = 0
$$

or

$$
frac 1xsum_k=1^inftya_k x^k - 2sum_k=0^inftya_k x^k-sum_k=0^infty(-1)^k x^k = 0
$$

now assuming $|x| < 1$ we have

$$
frac 1x (G(x)-a_0)-2G(x)-frac1x+1=0
$$

and

$$
G(x) = fraca_01-2x+frac 13frac11-2x-frac 13frac11+x
$$

etc.

share|cite|improve this answer

answered Mar 21 at 22:48

CesareoCesareo

9,7263517

$endgroup$

add a comment | 

$begingroup$

Hint.

Calling

$$
G(x) = sum_k=0^inftya_k x^k
$$

we have

$$
a_k+1x^k-2a_k x^k -(-1)^k x^k = 0
$$

or

$$
frac 1xsum_k=1^inftya_k x^k - 2sum_k=0^inftya_k x^k-sum_k=0^infty(-1)^k x^k = 0
$$

now assuming $|x| < 1$ we have

$$
frac 1x (G(x)-a_0)-2G(x)-frac1x+1=0
$$

and

$$
G(x) = fraca_01-2x+frac 13frac11-2x-frac 13frac11+x
$$

etc.

share|cite|improve this answer

answered Mar 21 at 22:48

CesareoCesareo

9,7263517

$endgroup$

share|cite|improve this answer

answered Mar 21 at 22:48

CesareoCesareo

9,7263517

answered Mar 21 at 22:48

CesareoCesareo

9,7263517

answered Mar 21 at 22:48

CesareoCesareo

9,7263517