Intereting Posts

$f(0)=f'(0)=f'(1)=0$ and $f(1)=1$ implies $\max|f''|\geq 4$
Show that if $c_1, c_2, \ldots, c_{\phi(m)}$ is a reduced residue system modulo m, $m \neq 2$ then $c_1 + \cdots+ c_{\phi(m)} \equiv 0 \pmod{m}$
Integrals of the form ${\large\int}_0^\infty\operatorname{arccot}(x)\cdot\operatorname{arccot}(a\,x)\cdot\operatorname{arccot}(b\,x)\ dx$
Showing $f_{n}$ is a normal family, where $f_{n}$ is the $n^{th}$ iterate of $f$
How to avoid stupid mistakes in calculus exams without checking the whole process?
How can I get a irreducible polynomial of degree 8 over $Z_2$?
Proof of the progressiveness of a stopped progressive process
Parallel transport along a 2-sphere.
Textbook Recommendation: Topological Dynamics
Writing number as sum of reciprocals of factorial
Coordinate ring of zero locus of unit circle
Finding the heat flow across the curved surface of a cylinder
Defining a Free Module
What's the problem this logic
Sufficient conditions for being a PID

I’m having some difficulty understanding ‘Linear Homogeneous Recurrence Relations’ and ‘Inhomogeneous Recurrence Relations’, the notes that we’ve been given in our discrete mathematics class seem to be very sparse in terms of listing each step taken to achieve the answer and this makes it incredibly hard for people like myself who are not of a maths background to understand (I’m a computer science student, not a maths student) and I guess my main problem is that I don’t understand the notes, as they some to jump steps due to assumed maths knowledge and this is troubling for me coming from a purely computer science background.

I was wondering if somebody could write out the steps in order to achieve the answers for these types of questions?

I’ve searched around on youtube and google on guides of how to do them, but they all differ slightly from the one’s that we are supposed to learn, and I don’t want to learn the wrong thing. I’m not sure if maybe my lecturer has called it something slightly different, but if somebody could help me out, that’d be great.

- Computation with a memory wiped computer
- Computing the $n^{\textrm{th}}$ permutation of bits.
- Is the $24$ game NP-complete?
- How to maximize the number of operations in process
- Proof that Newton Raphson method has quadratic convergence
- Testing Zeros Of The Riemann Hypothesis

An example question in the notes for Linear Homogeneous Recurrence Relations is:

*1. Find the solution of:*

with

And an example of Inhomogeneous Recurrence Relations would be:

*2. Find a particular solution of:*

Here is a second example for a more complicated linear homogeneous recurrence relation:

*3. Find the solution:* $ a_{n} = a_{n-1} + a_{n-2}$ with $a_{0} = 0 \ and \ a_{1} = 1 $

The lecturer came up with the general solution of $a_{n} = c\left ( \frac{1+\sqrt{5}}{2} \right )^{n} + d\left ( \frac{1+\sqrt{5}}{2} \right )^{n}$

And I just can’t see how he got here, is there some way that he has worked this out, or is it pure deduction?

- Counting non-isomorphic relations
- What is the best book for studying discrete mathematics?
- How can we draw $14$ squares to obtain an $8 \times 8$ table divided into $64$ unit squares?
- loop invariant fibonacci
- How to prove a total order has a unique minimal element
- How to Handle Stronger Induction Hypothesis - Strong Induction
- Questions on Erdős–Ginzburg–Ziv theorem for primes and understanding related lemmas and their applications.
- Odd/Even Permutations
- Sum of cubes proof
- Odd binomial sum equality has only trivial solution?

Are you familiar with differential equations? Solving linear recurrences is the same as solving linear differential equations, essentially. Linear recurrences (ie., difference equations) are discrete differential equations.

So for $a_{n} = 4a_{n-1} – 3a_{n-2}$, we start by setting up our characteristic polynomial: $\lambda^{2} – 4\lambda + 3 = 0$. You then solve for $\lambda$, getting solutions $\lambda = 1, 3$. And so your general form equation $a_{n} = c_{1}(\lambda_{1})^{n} + c_{2}(\lambda_{2})^{n}$.

To set up the characteristic polynomial, you look at the difference of the indices. So for $a_{n}$, we see indices $n, n-1, n-2$. Clearly there is a difference of two between the largest and smallest index. So we have a quadratic. The largest indexed term has the largest power. So $a_{n} \to \lambda^{2}$, $4a_{n-1} \to 4\lambda$, and $-3a_{n-2} \to -3$. Do you see how I got that?

So $a_{n} = c_{1} + c_{2}3^{n}$. Then plug in your constraints and solve for $c_{1}$ and $c_{2}$.

Now for your example with Fibonacci, we have $a_{n} = a_{n-1} + a_{n-2}$, we have another quadratic. Do you see why? So $a_{n} \to \lambda^{2}$, $a_{n-1} \to \lambda$, $a_{n-2} \to 1$. And so our characteristic polynomial is $\lambda^{2} – \lambda – 1 = 0$. Solve for $\lambda$, which gives you two distinct roots $\lambda_{1}, \lambda_{2}$, then plug in: $a_{n} = c_{1} \lambda_{1}^{n} + c_{2}\lambda_{2}^{n}$ and solve the system of equations from your initial conditions.

Now for a first order non-homogenous recurrence of the form $a_{n} = ra_{n-1} + c$, we get a solution of the form $a_{n} = kr^{n} + c \frac{r^{n}-1}{r -1 }$ for $r \neq 1$. If $r = 1$, we get $a_{n} = k + cn$.

The constant $k$ is what we solve for based on the initial conditions.

A *linear recurrence equation* for $a_r$ is one of the form:

$$

f_n(r) a_{r + n} + f_{n – 1}(r) a_{r + n – 1} + \cdots + f_0(r) a_r = g(r)

$$

Here the $f_i(r)$ and $g(r)$ are arbitrary functions of $r$. If $f_n \ne 0$ and $f_0 \ne 0$, it is called of $n$-th order. If $g = 0$, it is called *homogeneous*.

If the $f_i$ are constants, it is a *linear recurrence with constant coefficients*, which are specially nice to handle.

Only general linear recurrences of the first order can be solved exactly, higher orders with non-constant coefficients can get quite hairy.

- Ideal of the pullback of a closed subscheme
- Prove by induction that $n^5-5n^3+4n$ is divisible by 120 for all n starting from 3
- Probability of picked cards to be smaller than the largest picked card
- Prove that the equation $18x+42y=22$ has no integer solution?
- Book(s) Request to Prepare for Algebraic Number Theory
- $f_n$ converges uniformly on $$ to some function $f$
- How many different sizes of infinity are there?
- Given $f ( x ) = x^n + a_{1} x_{n − 1} + ··· + a_{n − 1} x + a_n$, find the discriminant of the these polynomials
- Proof of trigonometric identity $\sin(A+B)=\sin A\cos B + \cos A\sin B$
- Integration with a constant “a”: $ \int_0^a \frac1{\sqrt {a^2-x^2}} dx $
- Prove that every group $G$ has a unique maximal perfect subgroup $R$ and $R$ is fully-invarinat in $G$
- Proof by induction – correct inductive step?
- Why is closure omitted in some group definitions?
- Topological vector space with discrete topology is the zero space
- Prove that $\lim_{x \rightarrow 0} \mathrm {sgn} \sin (\frac{1}{x})$ does not exist.