So I have the following formula for the coefficient of the recursion and I am trying to find an explicit formula for $a_n$ the nth coefficient:  $$ a_n = (n+1)a_{n-1} + 3^n $$  $$ a_0 = 1; \space\space\space n\geq1  $$   Here's what I have done so far (I may be incorrect in some intermediate steps, I am not sure):  expand the $(n+1)$ term so that we have $ a_n = na_{n-1} + a_{n-1}+ 3^n $, multiply all sides by $ \frac{x^n}{n!}$ and sum over $ n $ giving the following:   $$\sum_{n \geq1}{a_n\frac{x^n}{n!}} = \sum_{n \geq1}n a_{n-1}\frac{x^n}{n!} + \sum_{n \geq1} a_{n-1}\frac{x^n}{n!} + \sum_{n \geq1}3^n\frac{x^n}{n!} $$  Let's call the exponential generating function $\sum_{n \geq0}{a_n\frac{x^n}{n!}} = G(X)$ $$ \therefore G(x) = xG(x) + xe^x + 3^ne^x - 3^n +1 $$  and this simplifies to: $$ G(x) = \frac{x}{1-x}e^x + \frac{3^n}{1-x}e^x + \frac{3^n}{1-x} + \frac{1}{1-x}$$  I am quite stuck here, for the first term on the RHS I have: $\sum_{i = 0}^{n-1} \frac{n!}{i!}$ for the second term I have $3^n\sum_{i = 0}^{n-1} \frac{n!}{i!} $ for the third term I have $3^n  \sum_{n\geq0} x^n$ and for the final term I have $\sum_{n\geq0} x^n$ (so taking the coefficients of the x terms we get:  $$a_n = \sum_{i = 0}^{n-1} \frac{n!}{i!} + 3^n\sum_{i = 0}^{n-1} \frac{n!}{i!} + 3^n + 1$$  which gives the wrong answer... can anyone help me out see where I went wrong?  Thank you!  edit: I realize there is a post asking the same question which uses integration/differentiation; I am trying to do this without the use of calculus.
120508
Given $a_0 = 1$ and $a_n = (n + 1)a_{n - 1} + 3^n$ for $n \geq 1$, find formula for $a_n$.   First remind the definition of power series $F(x) = \sum_{n \geq 0}f_n \frac{x^n}{n!}$ and exponential generating function $G(x) = \sum_{n \geq 0}\frac{x^n}{n!} = e^x$   Note we have to use exponential generating function to solve this question. So let $f(x) = \sum_{n \geq 0}a_n\frac{x^n}{n!}$, multiplying both sides of  $a_n = (n + 1)a_{n - 1} + 3^n$ by $\frac{x^n}{n!}$ and sum over all $n \geq 1$. We get, $$\sum_{n \geq 1}a_n\frac{x^n}{n!} = \sum_{n \geq 1}(n + 1)a_{n - 1}\frac{x^n}{n!} + \sum_{n \geq 1}3^n\frac{x^n}{n!}$$ $$\sum_{n \geq 1}a_n\frac{x^n}{n!} = \sum_{n \geq 1}na_{n - 1}\frac{x^n}{n!} + \sum_{n \geq 1}a_{n - 1}\frac{x^n}{n!} + \sum_{n \geq 0}\frac{(3x)^{n}}{n!} - 1$$ $$\underbrace{\sum_{n \geq 0}a_n\frac{x^n}{n!}}_{f(x)} - 1 = x\underbrace{\sum_{n \geq 1}a_{n - 1}\frac{x^{n-1}}{(n-1)!}}_{f(x)} + \underbrace{\sum_{n \geq 1}a_{n - 1}\frac{x^{n}}{(n)!}}_{\int{f(x)} = F(x) + C} + e^{3x} - 1$$ $$F'(x) - 1 = xF'(x) + F(x) + e^{3x} - 1   + C$$ $$F'(x)(1 - x) - F(x) = e^{3x} + C$$ I think I'm essentially stuck here, I'm trying my best to manipulate each term so that we can express each term in terms of $f(x)$. But I can't go further from here because it doesn't like look this form can lead us to the solution.   Any feedback or suggestion?
118752
The ordinary generating function for the central binomial coefficients, that is, $$\displaystyle \sum_{n=0}^{\infty} \binom{2n}{n} x^{n} = \frac{1}{\sqrt{1-4x}} \, , \quad |x| &lt; \frac{1}{4},$$ can be derived by using the duplication formula for the gamma function and the generalized binomial theorem. But what about the ordinary generating function for $ \displaystyle  \binom{3n}{n}$? According to Wolfram Alpha,   $$ \sum_{n=0}^{\infty} \binom{3n}{n} x^{n} = \frac{2\cos \left(\frac{1}{3} \arcsin \left(\frac{3 \sqrt{3x}}{2} \right)\right)}{\sqrt{4-27x}} \, , \quad |x| &lt; \frac{4}{27}. $$ Any suggestions on how to prove this? EDIT: Approaching this problem using the fact that $$ \text{Res} \Big[ \frac{(1+z)^{3n}}{z^{n+1}},0 \Big] = \binom{3n}{n},$$ I get $$ \sum_{n=0}^{\infty} \binom{3n}{n} x^{n} = -\frac{1}{2 \pi i x} \int_{C} \frac{dz}{z^{3}+3z^{2}+3z - \frac{z}{x}+1},$$ where $C$ is a circle centered at $z=0$ such that every point on the circle satisfies $ \displaystyle\Big|\frac{x(1+z)^{3}}{z} \Big| &lt; 1$. Evaluating that contour integral would appear to be quite difficult.
28325
Possible Duplicate:                I know that the sum of the squares of the first n natural numbers is $\frac{n(n + 1)(2n + 1)}{6}$. I know how to prove it inductively. But how, presuming I have no idea about this formula, should I determine it? The sequence $a(n)=1^2+2^2+...+n^2$ is neither geometric nor arithmetic. The difference between the consecutive terms is 4, 9, 16 and so on, which doesn't help. Could someone please help me and explain how should I get to the well known formula assuming I didn't know it and was on some desert island?
103852
Let $\{f_n(x)\}_{n\in \Bbb N}$ be a sequence of polynomials defined inductively as   $$\begin{matrix} f_1(x) &amp; = &amp; (x-2)^2 &amp; \\ f_{n+1}(x)&amp; = &amp; (f_n(x)-2)^2, &amp;\text{ for all }n\ge 1.\end{matrix}$$      Let $a_n$ and $b_n$ respectively denote the constant term and the coefficient of $x$ in $f_n(x)$. Then         $(\text A)\,\, a_n=4, b_n=-4^n$   $(\text B)\,\,a_n=4, b_n=-4n^2$   $(\text C)\,\, a_n=4^{(n-1)!}, b_n=-4^n$   $(\text C)\,\, a_n=4^{(n-1)!}, b_n=-4n^2$      Please help me how to solve this problem. I am not able to solve it.  The problem can be found on this .
93551
I'm asked to      find a power series of the form $\sum a_n x^n$, recognize the resulting series as the expansion of a familiar function, then verify my conclusion by solving the equation directly.     Given $xy'=y$.  However, I'm getting $a_0\sum_{n=0}^\infty (n! x^n)^{-1}$, which doesn't appear to match any functions that I know right now at least.  (I was also expecting something involving $e$ just from looking at it.)  Here's what I got so far:  $$let \ \ y = \sum_{n=0}^\infty a_n x^n$$ $$y'=\sum_{n=1}^\infty na_nx^{n-1}$$ $$xy'=\sum_{n=1}^\infty na_nx^n$$ and since $xy'=y$: $$\sum_{n=1}^\infty na_nx^n=\sum_{n=0}^\infty a_n x^n$$ $$\sum_{n=1}^\infty na_nx^n=\sum_{n=1}^\infty a_{n-1} x^{n-1}$$ $$na_nx^n=a_{n-1} x^{n-1}$$ $$a_nnx=a_{n-1}$$ $$a_n=\frac{a_{n-1}}{nx}$$  taking $a_0=a_0$  $$a_1=\frac{a_0}{x}, \qquad a_2=\frac{a_0}{2x^2} \qquad a_3=\frac{a_0}{6x^3}$$  and generally,   $$\sum_{n=0}^\infty \frac{a_0}{n!x^n}$$  Where did I go wrong?
73670
Knowing that $z + \frac{1}{z} = 3$ ($z \in \mathbb{R}$), prove that $z^n + \frac{1}{z^n} \in \mathbb{Q}$ ($n \in \mathbb{N}$ and $n \geq 1$).  I've tried to find a general formula for $z^n + \frac{1}{z^n}$. $$\left(z + \frac{1}{z}\right)^n = \binom{n}{0}z^n + \binom{n}{1}z^{n-2} + ... + \binom{n}{n-1}z^{2-n} + \binom{n}{n}z^{-n}$$ $$\left(z + \frac{1}{z}\right)^n = \binom{n}{0}(z^n + z^{-n}) + \binom{n}{1}(z^{n-2} + z^{2-n}) + ...$$  However, this formula seems to be wrong and I currently have no idea how to correct it and what to do next.  Thank you in advance for your help!
84065
I would appreciate a little help in finalizing a proof for the following:  Let $a_n$ be the sequence defined as $a_1 = 1$, $a_2 = 8$, and $a_n = a_{n-1} + 2*a_{n-2}$ when $n \geq 3$. Prove that $a_n = 3*2^{n-1} + 2(-1)^n$.  I decided to use strong induction and show that if the statement is true for $1,...,n$ , then it is true for $n+1$ (going off the fact that the statement is true for $n=3$). I have: $$a_{n+1} = a_n + 2*a_{n-1} = 3*2^{n-1} + 2(-1)^n + 2(3*2^{n-2} + 2(-1)^{n-1}) = 3*2^n + 2(-1)^n + 4(-1)^{n-1}$$  Which is close to the result I want $(3*2^n + 2(-1)^{n+1})$ but the signs are switched for the $(-1)$ terms; therefore I suspect I missed a $-1$ somewhere, but I could not see where the error is.  I appreciate all and any help. Thank you kindly!
92609
Usually, the Stirling numbers of the first kind are defined as the coefficients of the rising factorial: $(*) \prod_{i=0}^{n-1}(x+i) = \sum_{i=0}^{n} S(n,i) x^i$.   With this definition, a recursive relation of $S(n,i)$ be derived, and it can be shown that is coincides with the recursive relation on the number of permutation on an n-set with i cycles and they have the same initial conditions, hence they coincide.   1) Is there any possibility to do it the other way around, i.e., define $S(n,i)$ combinatorially and then to show that $\prod_{i=0}^{n-1}(x+i) = \sum_{i=0}^{n} S(n,i) x^i$ holds for $x \in \mathbb{N}$ by some combinatorial argument, and thus it is a polynomial identity?  (For Stirling numbers of the second kind, it is possible: it can be shown that $n^k = \sum_{i=0}^{k} \binom{n}{i} i! S_2(k,i)$ combinatorially ($n^k$ counts function from $[k]$ to $[n]$).)  2) Additionally: equating coefficients in $(*)$ shows that $S(n,i)$ is the elementary symmetric polynomial on $n$ variables of degree $n-i$ evaluated on $(0,1,\cdots ,n-1)$. Is there a combinatorial interpretation of this?
89786
Solve the following recurrence relation by generating its direct   formula: $$a_n = 3a_{n-1} + 2n, a_0 = 1$$   Use the direct formula to find the   $10th$ term of the recurrence relation.    My attempt:  $3(10-1) + 2(10)$  $3(9) +  20$  $27 + 20$  $10th$ term = $47$  Is this correct?
24080
How would you solve for the closed term form of $a(n)$ given the general form of the third order linear homogenous recurrence relation with real constant coefficients.  $a(n)-P\,a(n-1)-Q\,a(n-2)-R\,a(n-3)=0$  with the initial terms of a1, a2, and a3  and given that the roots of the characteristic equations have   two repeated roots and a real root three repeated roots   (can you give answers for both cases please)  For second order recurrence relations I know that you can use generating functions to deduce a closed form because it is then expressed as a arithmetic series which can be converted into a closed form.  However in the case of the general term of the third order recurrence relations if I follow the same steps what I did with the second order recurrence relation, instead of getting a simple arithmetic series I seemed to get a second order recurrence relation inside the series.  What am I doing wrong?  or is there a different method of approach in this case?  When I search the web I get these results  S(n) = nAx1^n + Bx1^n + Cx2^n,for the case when there are two repeated roots  and  S(n) = n^2Ax^n + nBx^n + Cx^n, for the case when there are three repeated roots  I just don't know how to get to these results  Please help
97651
I want to examine and hopefully deduce a formula that generates all $n\geq0$ for which $n\cdot2^n+1$ is divisible by $3$. Let's assume that it is true for all $n$ and that there exist a natural number $k\geq0$ such that $$n\cdot2^n+1=3k,$$  Now I want to proceed with induction, but clearly this will not work because for $n=3$ we have $3\cdot2^3+1=3\cdot8+1=24+1=25$ which is clearly not divisible by $3$.   Any ideas how to evaluate a formula that generates all the $n$'s for which $n2^n+1$ is divisible by $3$?
115519
Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$.   i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove $$\sum_{k=0}^n \binom nk = 2^n.$$ Hint: use induction and use Pascal's identity  What I have so far: $$p(n)= \sum^{n}_{k=0}{n\choose k} = 2^n$$ $$P(0)=\sum^{0}_{k=0}{0\choose k} = 2^0$$ LHS: ${0\choose k}=1$ RHS $2^0=1$  now of for the inductive step I am getting all tangled up in my terms. It seems like a silly thing to get confused on but every inductive proof I've done I do $P(n) =$ something to $P(1)$ then my inductive step is $P(k)$ and $P(k+1)$ but I don't think can use that terminology because those variables are in the problem. Also the two (i.e) are throwing me off, am i even setting it up right to begin with or am I missing something. How does $(x+y)^n$ even fit in to here, I know how it connects to pascals because I googled it but I don't understand how it fits into my inductive proof.  I need help getting on track form here. PS my professor is a stickler for set up so making sure I write it properly is a big part of it.
29076
I have a Recurrence: $$a_{0}=1$$ $$  a_{n}=\sum_{k=0}^{n-1}(n-k)a_{k}$$ I have evaluated some a's:$a_{0}=1, a_{1}=1,a_{2}=3,a_{3}=8,a_{4}=21,a_{5}=55,...$. In the previous exercise on had to derive a generating Function for the even indexted Fibonacci Numbers. So these are definitely $F_{0}=1,F_{1}=1,F_{2}=3,F_{3}=8,F_{4}=21,...$   Then I had a detailed look on the summation: $$a_{0}=1$$ $$a_{1}=(1-0)*1=1$$ $$a_{2}=(2-0)*a_{0}+(2-1)*a_{1}=2*1+1*1=3$$ $$a_{3}=(3-0)*a_{0}+(3-1)*a_{1}+(3-2)*a_{2}=3*1+2*1+1*3=8$$ $$a_{4}=(4-0)*a_{0}+(4-1)*a_{1}+(4-2)*a_{2}+(4-3)*a_{3}=4*1+3*1+2*3+1*8=21$$  Its obviously linked to:    But i dont see how to proceed.
50623
Purely for my own amusement I've been playing around with the .  The Ackermann function is a non primitive recursive function defined on non-negative integers by:  $A(m,n) = n+1$, if $m=0$  $A(m,n) = A(m-1,1)$, if $m&gt;0$ and $n=0$  $A(m,n) = A(m-1,A(m,n-1))$, if $m&gt;0$ and $n&gt;0$  I'm not interested in values of the function itself, rather I'm interested in the number of recursions the function takes to arrive at a value. For example:  $A(1,2) = A(0,A(1,1)) = A(0,A(0,A(1,0))) = A(0,A(0,A(0,1))) = A(0,A(0,2)) = A(0,3) = 4$  That's 6 steps, so if we define $RA(m,n)$ as the number of recursions to calculate $A(m,n)$, then $RA(1,2) = 6$.  I made a short Excel macro to calculate $RA(m,n)$ for any given $m$ and $n$. The problem I have is that $RA(m,n)$ grows even faster than $A(m,n)$ and I quickly run out of stackspace. The table below shows $RA(m,n)$ for very small values of $m$ and $n$. The numbers shown for $RA(3,10)$ and $RA(4,1)$ are the number of steps before crashing!    A formula for $RA(1,n)$ is trivial, and it is relatively easy to see that $RA(2,n) = 5(n+1) + 4n(n+1)/2$.  So my questions: can anyone see an explicit formula for $RA(3,n)$? More generally, does a formula exist for $RA(m,n)$, in the same way that $A(m,n)$ can be expressed using Knuth arrows?   For the low values shown of $m$ and $n$, $RA(m,n)$ looks about order of magnitude larger than $A(m,n)$. Can we prove that $RA(m,n) &gt; A(m,n)$ for all $m,n$. Intuitively, it should be.  For bonus points, can $RA(m,n)$ be expressed in terms of $A(m,n)$?
24132
Find $$S=\sum_{r=1}^{3n-1}{ (-1)^{r-1}r\over{3n \choose r}},~ \text{if $n$ is even}$$  The answer given to me is ${3n\over3n+2}$ , the main problem I am facing is that the binomial coefficients are in the denominator, and so I can not use any of the usual techniques I used to use , like using integration or different on any binomial series. Although I tried by rewriting the sum in reverse order and then adding it to the original expression, this gave me : $$2S=3n\sum_{r=1}^{3n-1}{ (-1)^{r-1}\over{3n \choose r}}$$ This is sure simpler than the original problem but still no good , I could not figure out a way to solve the rest . Could someone please help me in solving thi problem ? Thanks !
49994
I am trying to see where this relationship comes from: $\displaystyle \sum_{n=0}^{\infty}\frac{x^n}{n!} = e^x$ Does anyone have any special knowledge that me and my summer math teacher doesn't know about? He went over generating functions a few days ago and I did not know exactly what he was talking about. In the middle of his lecture he wrote this generating function. He explained that in this case $a_{n} = \frac{1}{n!}$ for $\displaystyle \sum_{n=0}^{\infty} a_{n} x^n$.   Is the relationship a definition or can it be derived using $\displaystyle \sum_{n=0}^{\infty} x^n $?
81346
It is not hard to show, by induction on $m\in\mathbb N$, that there exist a sequence $(B_n)_{n\geq0}$ of rational numbers such that  $$\sum_{k=1}^nk^m=\frac1{m+1}\sum_{k=0}^m\binom{m+1}kB_k\,n^{m+1-k},\ \style{font-family:inherit;}{\text{for all}}\ n\geq1\,.$$  These are the Bernoulli numbers of the second kind, that is, $B_1=+1/2$. A corollary of the proof (by induction) of the fact above is a recurrence formula for such numbers $B_n$, which are known as Bernoulli numbers:  $$\sum_{k=0}^{n-1}\binom nkB_k=0\,.\tag{$\ast$}$$  On the other hand, there are a number of explicit formulae for $B_n$, which are obtained using the equality $\frac x{e^x-1}=\sum_{n=0}^\infty B_n\,\frac{x^n}{n!}$; see  and . For example:  $$B_n=\sum_{k=0}^n\frac1{k+1}\sum_{r=0}^k(-1)^r\binom krr^n\,.\tag{$\ast\ast$}$$  Is there some clever way to manipulate the recurrence $(\ast)$ in order to obtain $(\ast\ast)$?