# Tagged Questions

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

33 views

23 views

### Recurrence relations - walk on a graph

given the following undirected graph: I need to find a recurrence relation that describes the number of possible walks starting at point A. Well, naive me Iv'e defined $a_n$ and tried to find ...
40 views

72 views

### Very confused by recurrence relations as a concept

We've been introduced to recurrence relations as a concept in my Discrete class. One question asks: Given the recurrence: $S(1) = 1$, $S(n) = 2S(n − 1) + 3 (for \ n > 1)$ prove ...
12 views

81 views

### Find the $m$ such $a_{n+1}=a^5_{n}+487$ [closed]

Let $\{a_{n}\}$ be a sequence of positive integers, and suppose $a_{0}=m$. Further, $\{a_{n}\}$ satisfies $$a_{n+1}=a^5_{n}+487.$$ Find $m$ so that this sequence consists of square numbers for as long ...
15 views

63 views

Take: $$a_0=x,~~~~b_0=y$$ $$a_{n+1}=\frac{a_n+\sqrt{a_nb_n}}{2},~~~~b_{n+1}=\frac{b_n+\sqrt{a_nb_n}}{2}$$ Then we obtain as a limit the logarithmic mean of $x,y$: $$\lim_{n \to \infty} a_n=\lim_{n ... 1answer 87 views ### Limit and rate of convergence of the sequence a_{n+1}=\frac{a_n^2+b_n^2}{a_n+b_n},~~b_{n+1}=\frac{a_n+b_n}{2} Define the sequence the following way for some x,y \geq 0:$$a_0=x,~~~~~~~b_0=ya_{n+1}=\frac{a_n^2+b_n^2}{a_n+b_n},~~~~~~b_{n+1}=\frac{a_n+b_n}{2}$$Obviously:$$a_n \geq b_n,~~~~n \geq 1$$... 0answers 50 views ### How do I show the relationship between I_n:=\int_{0}^{\pi}sin(x)^ndx and I_n:=\frac{n-1}{n}I_{n-2} How do I show the relationship between$$I_n:=\int_{0}^{\pi}sin(x)^ndx$$and$$I_n:=\frac{n-1}{n}I_{n-2}$$for when n \in \mathbb{N} and n≥2 1answer 34 views ### Recursive to non recursive function$$ f(x) = \begin{cases} 0 & x=1 \\ f(x-1)+1 & \frac{f(x-1)}{x-1} < p \\ f(x-1) & \text{otherwise} \\ \end{cases} $$Where p is a constant less that or equal to 1. And x is a whole ... 0answers 63 views ### Does there exist a closed form for this recurrence? This question follows from my previous inquiry: On the convergence of a more complex iterated radical. My question here is very similar, except I now understand why my previous method is insufficient. ... 4answers 106 views ### How many words of length n can we make from 0, 1, 2 if 2's cannot be consecutive? How many words we can make from 0,1,2? The restriction is we can't put the digit 2 after the digit 2. My solution: I tried to solve it with Inclusion-Exclusion Principle. Count the number of ... 4answers 790 views ### How to find explicit formula for two recursions? I have to find explicit solution for two intertwining recursions$$\begin{align} f(n)&=f(n-2)+2g(n-1) \\ g(n)&=g(n-2)+f(n-1) \end{align}$$for f(0)=1, f(1)=0, g(0)=0 ,g(1)=1. What ... 1answer 25 views ### Exponential decay + a recurrence relation I'm not sure if I get this right, some pointers could be helpful. Say you have to take 60m of some sort of medication at midnight. It has a blood half-life of 6 hours. Meaning that after 24 hours 3.... 2answers 31 views ### How many bit strings of length N are there such that the all ones lie within a window of length K? Out of all bit strings of length N, we need to count how many of them are there in which all the ones are present in a window of length K. For this, my initial thought was: The starting point of ... 3answers 270 views ### How can I find an explicit expression for this recursively defined sequence? We define the sequence (u_n)_{n=1}^\inftyby:$$u_{n+1}=1+\frac{1}{u_n}$$How can I find the limit of this sequence as it goes to infinity? By induction, I can prove that it is bounded above and ... 0answers 28 views ### Solving differential recurrence equations I played around trying to make an equation describing Fibonacci numbers and ended up finding out that what I'd created was something called a recurrence equation: f(x)=f(x-1)+f(x-2) (f(x) is ... 4answers 317 views ### Limit of x_n^3/n^2 when x_{n+1}=x_n+ 1/\sqrt {x_n} with x_0 \gt 0 Let (x_n)_{n \ge 0} a sequence of real numbers with x_0 \gt 0 and x_{n+1}=x_n+ \frac {1}{\sqrt {x_n}}. Check the existence and find$$L=\lim_{n \rightarrow \infty} \frac {x_n^3} {n^2}$$... 2answers 39 views ### How to solve this homogeneous recurrence relation of 2nd order? I have this homogeneous recurrence relation: x_n = 3x_{n-1} + 2x_{n-2} for n \geq 2 and x_0 = 0, x_1 = 1. I form the characteristic polynomial: r^2 - 3r -2 = 0 which gives the roots r = \... 3answers 62 views ### Solving a recurrence relation with n squared I have trouble solving the following recurrence:$$a_{1}=1, a_{n}=a_{n-1}\cdot n^{2}$$for n>1. It seems somewhat untypical to me, could you give me some general advice on dealing with such ... 2answers 90 views ### Functional Equation of iterations Problem: Let f : \mathbb{Q} \to \mathbb{Q} satisfy$$f(f(f(x)))+2f(f(x))+f(x)=4x$$and$$f^{2009}(x)=x ($f$ iterated $2009$ times). Prove that $f(x)=x$. This is a contest type problem ...
I have the homogeneous recurrence relation $x_n = x_{n-2}$ for $n \geq 2$ with $x_1 = 2$ and $x_0 = 1$. So for the characteristic polynomial I got $r^2 - r = 0$, then I factored out r: $r(r - 1)$ for ...
### Recurrence relation in $2$ variables [closed]
Given a recurrence relation $func(n,k) = func(n-1,k) + func(n-1,k-1)$ with base cases $func(n,1) = n$ and $func(1,k) = 1$. How can I obtain its solution?