# Tagged Questions

Questions regarding functions defined recursively, such as the Fibonacci sequence.

249 views

### Result of a $2D$ random walk with position dependent probabilities

I was just wondering about $2D$ random walks when I got the idea of a position dependent $2D$ random walk: A man is initially at $(x,y)$ and can move in a line parallel to the X and Y-axis only. ...
80 views

40 views

### Find a recurrence relation and solve it

Let $a_n$ be the nummber of ways that 4 people can throw $n$ eyes together with a die. Every person throw once. Now I want to find a generating function and compute $a_n$ for different $n$. To do ...
248 views

### Solving Recurrence Relations with Geometric Series

If given the following problem... $$4T \left(\frac n2\right) + c$$ after getting the pattern down you see the following $$4^k T\left(\frac {n}{2^k}\right) + 3^{k-1}c + 3^{k-2} c + \cdots + 3c + c$$ ...
49 views

### How to solve recurrence relation $a_{k}=7a_{k-1}-10a_{k-2}, \forall k\ge2$ with $a_{0} = a_{1} = 2$

Unfortunately I have no idea where to even start with this. This is my first math class in almost a decade. Can anybody tell me how i would go about solving for the following recurrence relation? ...
41 views

### Directly Obtaining the $n$th Value of a Lucas Sequence

(As an aside: This question lies relatively upon the border between the realms of Computer Science and Mathematics, and thus may be appropriate for StackOverflow as well.) I am in need of a method of ...
72 views

Solve the following recurrence relation: $f(1) = 1$ and for $n \ge 2$, $$f(n) = n^2f(n − 1) + n(n!)^2$$ How would I go about solving this? Would I need to find a substitution $f(n) =\text{ insert ... 1answer 112 views ### Solving a linear nonhomogeneous recurrence relation with troublesome$F(n)$I am trying to solve the following: $$a_n=5a_{n-1}-6a_{n-2}+2^n+3n$$ The general solution to the homogeneous equation is simple: $$a_n=5a_{n-1}-6a_{n-2} \rightarrow \\ r^2-5r+6=0 \rightarrow \\r=3,... 0answers 45 views ### Determining the sequence that yields a balanced search tree in the form of a recurrence / sequence Let's say I have a sequence of (distinct) monotonically increasing numbers S. I'll want to add them sequentially to a Binary Search Tree (BST) but as the numbers ... 1answer 19 views ### Recurrence Relations with Geometric Series if we have a situation where something is like this 2^k + c(2^{k-1} + 2^{k-2} + 2^{k-3} + ... + 1) since in this case r > 1 then in Computer Science we look at \sum_{i=1}^{n} r^{i} = \theta(... 1answer 56 views ### Solving recurrence relations with two variables whenever I've had to solve recurrence relations, I've kind of just messed around with it until it works. I have a more complicated case, and I was wondering if there are general strategies someone ... 1answer 48 views ### Simplified summation formula. Suppose I have the following recursive formula:$$A(n)=-\sum_{k=0}^{n-1}\binom{n}{k}\frac{1+(-1)^{n-k}+2(n-k)(-1)^{n-k-1}}{2}A(k)$$Then I can combine the negatives to get$$A(n)=-\sum_{k=0}^{n-1}\... 0answers 102 views ### What is the explicit formula (solution) to this recursively defined binary matrix? My question concerns the following binary matrix (call it matrix$A$). Or rather the entire family of such matrices, for some number of columns$n$and rows$2^n$. The ellipses indicate that the ... 4answers 116 views ### Solution verification: Prove by induction that$a_1 = \sqrt{2} , a_{n+1} = \sqrt{2 + a_n} $is increasing and bounded by$2I have the following recursive relation (sequence): \begin{align} a_1 = \sqrt{2}, \quad a_{n+1} = \sqrt{2 + a_n} \end{align} My Try: I'm a little skeptical of my manipulations near the end but it ... 0answers 65 views ### Generating function for recurrence in two variables Given characteristic polynomial for the recurrence in two variables (sayF(x,y)$) $$(y^2-1)^x$$ and initial values can generating function for$F(x,y)$be derived? I know how to do it for a ... 1answer 64 views ### Solve this recurrence relation Solve the following recursions:$a_{n+1}=3a_n-a_{n-1}-1$and$a_{n+1}=4a_n-a_{n-1}-1$. (These are to be solved separately, not simultaneously) I tried using generating functions but it got messy. Any ... 1answer 89 views ### How to prove the characteristic equation based solution of recurrence relations? What is the proof for / where might I find the proof to: Let$c_1, c_2,..., c_k$be real numbers. Suppose that the characteristic equation $$r^k-c_1 r^{k-1}-...-c_k=0$$ has$k$distinct roots$r_1, ...
I'm stuck on trying to prove that $T(n)= T(n-2)+k$ is bounded by $O(n)$ for all $n >1$ I expanded it out to reach the following guess: $T(n) = ((n-2)/2)k$ though when I try to prove ...