# recurrence relations [closed]

I have seen the following problem in my regular study, which I am not able to solve. Please solve it for me.

Let $C_0,..., C_{k-1}$ be fixed integers and consider the recurrence relation of order $k$, $X_{n+k} = C_{k-1} X_{n+k-1} + C_{k-2} X_{n+k-2} + \cdots + C_1 X_{n+1} + C_0 X_n$. Show that once $k$ values of $X_m$ are specified, all values of $X_n$ are determined.

Let $f(r) = r^k - C_{k-1} r^{k-1} - \cdots - C_0$; we call this characteristic equation (polynomial) of the recurrence relation. Show that if $f(p) = 0$ then $X_n = cp^n$ satisfies the recurrence relation for any $c$ belongs to $\mathbb{C}$ (complex member)

-

## closed as off-topic by Normal Human, Daniel Fischer♦, RecklessReckoner, Brad, TomásJul 19 '14 at 22:18

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Normal Human, Daniel Fischer, RecklessReckoner, Brad, Tomás
If this question can be reworded to fit the rules in the help center, please edit the question.

Try working with small values of n, and then try induction for a general proof. –  gary Aug 6 '11 at 5:18
You have posted several low-quality questions without accepting any answers on them. In addition, "please solve it for me" is not really in the spirit of this site: you should be here to learn, not just to copy answers. Think about what you don't understand, and ask about that instead. –  Qiaochu Yuan Aug 6 '11 at 5:19
Please format more clearly using $\LaTeX$. Then please do not assign homework-the imperative mode is offensive. Can you see why if you have $k$ values you have the rest? Then plug in the suggestion and see what happens. –  Ross Millikan Aug 6 '11 at 5:21

First Question

In general, it is not true that once $k$ values of $X_n$ are specified, all values of $X_n$ are determined. Here is a simple counterexample. There are many others.

Consider the recurrence $$X_{n+2}=0\cdot X_{n+1} +2X_n.$$ So, in the notation of the question, $k=2$. Let us specify that $X_0=2$ and $X_2=4$. This says absolutely nothing about $X_n$ when $n$ is odd.

Since what we were asked to prove is not true, let's try to prove something near what is asked for. To make typing easier, and so that all the symbols won't get in the way of the ideas, I will mostly use a concrete example.

Look for example at $$X_{n+3}=3X_{n+2}+5X_{n+1}+7X_n.\qquad\text{(Equation 1)}$$ and suppose that we know $X_m$ for three different values of $m$.

Note that if we knew $X_0$, $X_1$, and $X_2$, the first three values, then we could use Equation $1$ to calculate, one after the other, $X_n$ for all $n$.

So now suppose we know three values, but they are, say, $X_5$, $X_{22}$, and $X_{100}$.

Here is how we proceed, in principle.

The first three values are unknown. Call them $x$, $y$, and $z$. Use the recurrence to calculate the $X_n$, one after the other. Of course our answers will be in terms of the unknown $x$, $y$, and $z$. But the important thing to notice is that each $X_n$ is a simple linear combination of $x$, $y$, and $z$.

So a certain linear combination of $x$, $y$, and $z$, namely the one that gives $X_5$, has a known value. You should work out this linear combination, it can be done in two steps.

Similarly, one can in principle work out the linear combination that gives $X_{22}$, and the one that gives $X_{100}$. Now we have $3$ linear equations in the $3$ unknowns $x$, $y$, and $z$.

Solve these equations. Here we bump into a problem. Everything is OK if the matrix for the equations is invertible. However, it need not be, and then $(x, y, z)$ is not determined by $(X_5, X_{22}, X_{100})$.

However, "most of the time" the matrix will be invertible, and we will be OK. I could introduce more theory here, and mention Vandermonde determinants and their close relatives, but I doubt that you are expected to go that deep.

Consecutive values: If we know $X_m$ for $k$ consecutive values of $m$, then everything is determined. Suppose, for example, for our Equation $1$, we know $(X_{100}, X_{101}, X_{102})$. Then we can use Equation $1$ to calculate "forward", and find $X_{103}$, $X_{104}$, and so on.

But notice we can also work our way "backwards." Suppose we want $X_{99}$. Then using the fact that $$X_{102}=3X_{101}+ 5X_{100}+7X_{99}$$ we can solve the above equation of $X_{99}$, then do something similar to find $X_{98}$, and so on. We conclude that if $3$ consecutive values are known, everything is known.

The same idea works for general $k$. Maybe the question meant to say $k$ consecutive values, and the consecutive bit got left out!

Second Question: This one is straightforward. We want to show that putting $X_j=cp^j$ (for all $j$) "works."

Substitute $cp^j$ for $X_j$ in each side of the recurrence. We want to show that the two sides turn out to be the same: That's what it means for $X_j=cp^j$ to be a solution.

The left-hand side is $$cp^{n+k} \qquad \text{(Left Side)}$$ The right-hand side is messier. We get $$C_{k-1}cp^{n+k-1}+C_{k-2}cp^{n+k-2}+\cdots + C_0cp^n \qquad\text{(Right side)}$$

We want to show that the two displayed quantities are equal. Their difference is $$cp^{n+k}-C_{k-1}cp^{n+k-1}-C_{k-2}cp^{n+k-2}-\cdots - C_0cp^n$$ which is equal to $$cp^n\left(p^k -C_{k-1}p^{k-1}-C_{k-2}p^{k-2}-\cdots -C_0\right)$$ But the above expression is simply $cp^nf(p)$, which is $0$ since $p$ is a root of the characteristic polynomial.

-