Hot answers tagged

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*} So $a_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