# Tag Info

12

The way to do this without generating functions is to start with the ansatz that $$a_n = x^n$$ satisfies the recursion but possibly not the starting points at $n=0$ and $1$. If we have that solution then any $a_nkx^n$ satisfies the recursion as well. And if we have two such solutions $x^n$ and $y^n$ then any linear combination $a_n=kx^n+my^n$ will ...

6

This is called a linear homogeneous recurrence relation. If we look at the recursive case, we find that the coefficient of $a_{n-1}$ is $10$ and the coefficient of $a_{n-2}$ is $-21$. This means the "characteristic polynomial," which is basically the polynomial which tells us what the bases of the explicit formula will be, is like this: $$x^2-10x+21$$ Notice ...

4

Now because the sequence grows so quickly, it is easy to see that only the terms containing $a_m$ in the sum are going to be significant. Thus $a_{m+1} \approx (4m + 1) (a_m a_1 + a_1 a_m) \approx 8m a_m$. This tell us that $a_{m+1} \approx 8^m m!$. This initial guess can now be improved. It is possible to prove by induction that there exists constants \... 4 That method doesn't apply to this type of recurrence. For this one, it's probably simplest to work out the first few terms and guess the pattern. \begin{align*} a_0 &= 4\\ a_1 &= 4+7\cdot 1\\ a_2 &= 4+7\cdot 1+7\cdot 2\\ a_3 &= 4+7\cdot 1+7\cdot 2 + 7\cdot 3\\ \ldots \end{align*} Soa_n = 4+7(1+2+\cdots+n) = 4+7n(n+1)/2$4 This is a homogeneous linear recurrence relation with constant coefficients. From $$a_n = 10 a_{n-1} -21 a_{n-2}$$ you can infer the order$d=2$and the characteristic polynomial: $$p(t) = t^2 - 10 t + 21$$ Calculating the roots: $$0 = p(t) = (t - 5)^2 - 25 + 21 \iff t = 5 \pm 2$$ this gives the general solution $$a_n = k_1 3^n + k_2 7^n$$ The two ... 4 If the generating function is allowed, then this can be solved as follows: Define $$\color{blue}{f(x):=\sum\limits_{n=0}^\infty a_nx^n}.$$ Then from the recurrence relation, we have: $$a_nx^n=a_{n-1}x^n+7nx^n.$$ Summing over$n,$we have$f(x)-a_0=xf(x)+7\sum\limits_{n=1}^\infty nx^n.$Since $$\sum\limits_{n=1}^\infty nx^n=x\dfrac{d(1/(1-x))}{dx}=\dfrac{x}{(... 4 Let R be the right-shift operator: R = ( f \mapsto ( n \mapsto f(n+1) ) ). Then your equation is: (R-1)(a) = ( n \mapsto 7n ). Apply (R-1) to both sides repeatedly until the right-hand side vanishes! (R-1)^2 (R-1)(a) = ( n \mapsto 0 ). Now we can use the general solution for homogenous linear recurrence relations: a = ( n \... 3 Given$$ a_{n}-a_{n-1} = 7n $$it follows that:$$ a_N-a_0=\sum_{n=1}^{N}(a_{n}-a_{n-1})=\sum_{n=1}^{N}7n = 7\cdot\frac{N(N+1)}{2}$$so:$$ a_N = \color{red}{4+\frac{7N(N+1)}{2}}.$$3 This means$$ h_{n-1} = \frac{1}{2}(g_n - g_{n-1} - 3) \quad (*) \\ f_{n-1} = h_n -2h_{n-1}-2 \quad (**) $$So by applying (**) we can have$$ f_n = 2g_{n-1}+h_{n-1}+3 \iff \\ h_{n+1} -2h_n - 2 = 2g_{n-1}+h_{n-1}+3 \iff \\ 2 g_{n-1} = h_{n+1} -2h_n - h_{n-1} - 5 $$and by applying (*) it should be possible to come up with a recurrence in g terms only.... 3 Extending what Zach466920 said:$$\partial_t[k(t,n)]=F(n+1)\cdot k(t,n+1)\tag1$$We can develop a power series solution for this. Let$$k(t,n)=\sum_{m=0}^\infty \kappa(n, m)\ t^m$$We equation (1) as:$$\sum_{m=1}^\infty m\ \kappa(n, m)\ t^{m-1} =\sum_{m=0}^\infty(m+1)\ \kappa (n, m) \ t^m =F(n+1)\cdot\sum_{m=0}^\infty \kappa(n+1, m)\ t^m$$Which gives ... 2 The graph is bipartite, and the set that contains A contains only three vertices, so we can write a recurrence for them. Denoting the number of paths of length n that start at the mirror image of A by b_n and those that start at the lower centre vertex by c_n, we have$$ \pmatrix{a\\b\\c}_{n+2}=\pmatrix{3&1&1\\1&3&1\\1&1&1}\... 2 Obviously the claim is satisfied for$n=1$, as$S(1) = 2^{1+1} - 3 = 1$. Now assume that the claim is true for some$k \in \mathbb{N}$, then we have: $$S(k+1) = 2S(k) + 3 = 2(2^{k+1} - 3) + 3 = 2^{(k+1) + 1} - 6 + 3 = 2^{(k+1) + 1} - 3$$ Hence the proof. You've already been given the general form of the solutions. But in order to derive it on your own ... 2 Your first steps were correct. First, assume$x^{n}$with$x\neq0$is a solution. Plugging this into the recurrence, we get $$x^{n}=4x^{n-1}+21x^{n-2}.$$ Dividing through by$x^{n-2}$gives the quadratic $$x^{2}=4x+21.$$ This has roots$x=-3$and$x=7$. Since the recurrence is linear, any linear combination of solutions is also a solution. Therefore, we ... 2 There is a general tool to reason about various numbers of walks in an (undirected) graph - the adjacency matrix. If we have a graph$G$with adjacency matrix$A$, then the row of a vertex$v$in$A$tells us the number of length-1 walks to each other vertex. Similarly, the row of$v$in$A^2$tells us the number of length-2 walks, and so on, the row of$v$... 2 $$\begin{bmatrix} f_n \\ g_n \\ h_n \\ \end{bmatrix} = \begin{bmatrix} 0 & 2 & 1 \\ 0 & 1 & 2 \\ 1 & 0 & 2 \\ \end{bmatrix} \begin{bmatrix} f_{n - 1} \\ g_{n - 1} \\ h_{n - 1} \\ \end{bmatrix} + \begin{bmatrix} 3 \\ 3 \\ 2 \end{bmatrix}$$ This is an affine system that can be converted to a linear system with the usual trick: $$\... 2 It mostly amounts to using backwards the method that yields the formula of the Fibonacci sequence$$ca^{n+2}+db^{n+2}-ca^{n+1}-db^{n+1}-ca^n-db^n=\\ ca^n(a^2-a-1)+db^n(b^2-b-1)=\cdots\quad ?$$Of course, there are two things in the above expression that you do not want to calculate, and fortunately you need not do it. 1$$\sum_{i=1}^n(i\mod p)p^{n-i}$$You can split it into parts of size p to simplify it further. To find \displaystyle\sum_{i=1}^mip^{m-i}, all you have to do is find \sum p^k and then differentiate both sides with respect to p. \displaystyle\sum_{i=0}^{n-1}p^i=\frac{p^n-1}{p-1} \displaystyle\sum_{i=0}^{n-1}ip^{i-1}=\frac{np^{n-1}(p-1)-(p^n-1)}... 1 Your form for the particular solution is wrong, because it contains the solution of the homogeneous equation (B). Try An + B n^2. 1 The interesting bits are the initial condition and the recursion step from a n problem instance to a n+1 problem instance. If a_n is the number of paths of length n, starting at A or D, then a_0 = 2, thus (A) and (D), or a_1 = 2 + 2 = 4, thus (A,B), (A,C), (D,B), (D,C). Now looking at a_{n+1}: We can split a path of length n+... 1 I'm not quite sure why you assumed it would be in the form of x^n. This looks like a linear recurrence that can be solved using matrices to me. This is how we get a new term:$$\left[\begin{matrix}0 & 1 & 0 \\ 0 & 0 & 1 \\ -4 & 0 & 3\end{matrix}\right]\left[\begin{matrix} 0 \\ 0 \\ 18\end{matrix}\right]=\left[\begin{matrix}0 \\ 18 \\... 1 I assume you are OK with the idea that if we start with a$1$then we need to have a zero-pair among one fewer bits, thus there are$a_{n-1}$good strings. So Let's see what happens if we start with a$0$. We might have a$1$next, in which case we have "wasted" that starting zero, and have lost two bits, so there are only$a_{n-2}$good strings start with ... 1 If we assume that$a_0=0$and define$f(x)$as: $$f(x)=\sum_{n\geq 0} a_n x^{4n} \tag{1}$$ we have: $$f(x)^2 = \sum_{n\geq 0}\left(\sum_{k=0}^{n} a_k a_{n-k}\right) x^{4n}\tag{2}$$ as well as: $$x^4\cdot\frac{d}{dx}\left(\frac{f(x)^2}{x^3}\right) = \sum_{n\geq 0}(4n-3)\left(\sum_{k=0}^{n}a_k a_{n-k}\right)x^{4n} \tag{3}$$ and the recurrence relation ... 1 You appear to be doing things the hard way. That is, you seem to be trying to do the exercise Find a closed form for$S(n)$and working under the pretense that you don't alrady know what the closed form is. However, the problem you're asked to solve is: Here is the closed form for$S(n)$. Check that it's correct. which is a much easier problem. ... 1 You are on the right track. You're given a recurrence relation and asked to prove its closed form via induction. In your induction proof, when you consider$S(n+1)$, you will need to use the recurrence relation to invoke the$S(n)$case. 1 The Wiki reference shows that for$n>1$you can recover$F_n$as the (1,1) component of $$A^{n-1}= \begin{pmatrix}1 & 1\\ 1& 0\end{pmatrix}^{n-1} = \begin{pmatrix}F_n & F_{n-1}\\ F_{n-1}& F_{n-2}\end{pmatrix}$$ (you also could use the other elements). Now compute the matrix product$$\begin{pmatrix}F_n & F_{n-1}\\ F_{n-1}& F_{n-2}... 1 This should be the same as the linear systems we often get, just$y_n = A^n x.$Here the matrix$A$is square, you are calling it$d.$The Cayley-Hamilton Theorem says that$A$satisfies a polynomial, degree no larger than$d.$The same equation is satisfied by the column vectors$y_{k+d}, y_{k+d-1}, \ldots, y_k.$That is why the$d$entries of$y\$ each ...

Only top voted, non community-wiki answers of a minimum length are eligible