Question

@DLS

Answer 1

suppose \(G(x) = \sum\limits_{x=0}^{\infty} a_nx^n\)

Answer 2

can you express below in terms of \(G(x)\) ? \[\sum\limits_{x=0}^{\infty} \color{red}{a_{n+1}}x^n = ?\]

Answer 3

multiply divide by x ?

Answer 4

Exactly, could you do it all the way..

Answer 5

\[\sum\limits_{x=0}^{\infty} \color{red}{a_{n+1}}x^n =\dfrac{1}{x}\sum\limits_{x=0}^{\infty} \color{red}{a_{n+1}}x^{n+1} \]

Answer 6

next what

Answer 7

next what? :o

Answer 8

i want to express above series in terms of G(x)

Answer 9

so it becomes G(x)/x

Answer 10

wait wait

Answer 11

That is very wrong

Answer 12

G(x) + a0 / x ?

Answer 13

G(x) has the term \(a_0\)

but below has no \(a_0\) \[\sum\limits_{x=0}^{\infty} \color{red}{a_{n+1}}x^n =\dfrac{1}{x}\sum\limits_{x=0}^{\infty} \color{red}{a_{n+1}}x^{n+1} \]

Answer 14

Could you show me how

Answer 15

isn't the summation variable n ? :O

Answer 16

my mistake, fixed below \[\sum\limits_{n=0}^{\infty} \color{red}{a_{n+1}}x^n =\dfrac{1}{x}\sum\limits_{n=0}^{\infty} \color{red}{a_{n+1}}x^{n+1} \]

Answer 17

\[\sum\limits_{n=0}^{\infty} \color{red}{a_{n+1}}x^n =\dfrac{1}{x}\sum\limits_{n=0}^{\infty} \color{red}{a_{n+1}}x^{n+1} = \frac{1}{x}(G(x)+a_0)\]

Answer 18

that is wrong

Answer 19

my mistake, fixed below \[\sum\limits_{n=0}^{\infty} \color{red}{a_{n+1}}x^n =\dfrac{1}{x}\sum\limits_{n=0}^{\infty} \color{red}{a_{n+1}}x^{n+1} =\dfrac{1}{x}(a_1x^1+a_2x^2+\cdots ) \]

Answer 20

the stuff inside that parenthesis should be \(G(x) \color{red}{-}a_0\) right

Answer 21

yes

Answer 22

so we need to add 2*a0 ?

Answer 23

No

Answer 24

\[\sum\limits_{n=0}^{\infty} \color{red}{a_{n+1}}x^n =\dfrac{1}{x}\sum\limits_{n=0}^{\infty} \color{red}{a_{n+1}}x^{n+1} =\dfrac{1}{x}(a_1x^1+a_2x^2+\cdots ) = \dfrac{1}{x}(G(x)-a_0)\]

Answer 25

oh yes, sorry my bad

Answer 26

that is easy ok

Answer 27

using that, try solving below system :

\(a_n = 3a_{n-1} + 2b_{n-1}\)
\(b_n = a_{n-1} + 2b_{n-1}\)

Answer 28

notice, that system is same as

\(a_{n+1} = 3a_{n} + 2b_{n}\)
\(b_{n+1} = a_{n} + 2b_{n}\)

Answer 29

yes it is the same :)

Answer 30

You may start by letting the generating functions for \(a_n\) and \(b_n\) be \(G(x)\) and \(H(x)\) respectively

Answer 31

multiply \(x^n\) both sides of the recurrence relations,
and sum them from 0 to infinity

Answer 32

\[\sum_{n=0}^\infty a_{n+1}x^n = \sum_{n=0}^\infty3a_{n}x^n +\sum_{n=0}^\infty 2b_{n}x^n\]

Answer 33

we get :

\(\color{red}{\sum \limits_{0}^{\infty}}a_{n+1} ~x^n= \color{red}{\sum \limits_{0}^{\infty}}3a_{n} ~x^n+ \color{red}{\sum \limits_{0}^{\infty}}2b_{n}~x^n\)

\(\color{red}{\sum \limits_{0}^{\infty}}b_{n+1} ~x^n= \color{red}{\sum \limits_{0}^{\infty}}a_{n}~x^n + \color{red}
{\sum \limits_{0}^{\infty}}2b_{n}~x^n\)

Answer 34

\[\Large \frac{G(x) - a_0}{x} = 3 G(x) + 2 H(x)\]

Answer 35

substitute the previous formula formula

Answer 36

Yes!

Answer 37

\[\color{red}{\sum \limits_{0}^{\infty}}b_{n+1} ~x^n= \color{red}{\sum \limits_{0}^{\infty}}a_{n}~x^n + \color{red} {\sum \limits_{0}^{\infty}}2b_{n}~x^n \]
\[\Large \frac{H(x) - a_0}{x} = G(x) + 2H(x)\]

Answer 38

we get :


\(\dfrac{G(x)-a_0}{x}= 3G(x) + 2H(x)\)

\(\dfrac{H(x)-b_0}{x}= G(x) + 2H(x)\)

Answer 39

Collect the terms G and H in each equation

Answer 40

Remember, our goal is to solve \(G(x)\) and \(H(x)\)

Answer 41

and we have a linear system of two equations in terms of G(x) and H(x)

we can solve it easily

Answer 42

yes..suppose we get both G(x) and H(x)

Answer 43

we're done

Answer 44

once you have the generating functions G(x) and H(x) independently, you know what to do next to solve the recurrence relation

Answer 45

oh yes :) this was also easy :D

Answer 46

look at 2nd reply
http://math.stackexchange.com/questions/369377/solving-two-simultaneous-recurrence-relations

Answer 47

btw there was a typo in 5th line in that reply, he wrote 2A(z) instead of 3A(z)

Answer 48

yeah I just noticed :P nonetheless the procedure is exactly the same

Answer 49

Yes

Answer 50

and in that question yesterday, where we were supposed to count the solutions using G((x) , things can get pretty nasty when there are constraints on all 5 variables, G(x) may nor may not be easy to solve..is there something that can be done in the exam using calculator or something ? :| or should I leave it as "The answer is the coefficient of x^blah blah in this equation) ?

Answer 51

they cookup problems such that finding the coefficient would be easy

Answer 52

they test whether you know the method or not

Answer 53

testing ur algebra skills is pointless in an exam

Answer 54

yeah I guessed so :D it should be easy then.
BTW I have been trying this for a while :
Prove using binomial theorem >
\[\Large \sum_0^n C(n,r) 2^r = 3^n\]
I am unsure how to proceed with BT in this proof actually, any hints ?

Answer 55

that is very easy

Answer 56

expand below using binomial theorem :

\[(1+2)^n\]

Answer 57

\[3^n = (1+2)^n = \sum\limits_{r=0}^n C(n,r)1^{n-r}2^r = \sum\limits_{r=0}^n C(n,r)2^r \]

Answer 58

that is an one line proof

Answer 59

lol didn't think of that :O amazing :P
why is this of 6 marks nevermind :p

Answer 60

using same reasong, try proving below :
\[\sum\limits_{r=0}^n C(n,r)=2^n\]

Answer 61

yeah that's the expansion of (1+x)^n with x = 1

Answer 62

I guess I should avoid thinking too complex :|

Answer 63

Yep!

Answer 64

trust that your professor loves you and gives only problems that you're familiar with :)

Answer 65

hahah..its not true in case of my college, if they aren't in a good mood they would either make the paper difficult or there would be mistakes in the question. :|
there was a mistake in a 2 questions in my maths exam, and I spent a lot of time wasting on them :/ hopefully tomorrow will be good :)