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

learn more… | top users | synonyms (2)

2
votes
3answers
39 views

How can I rewrite recursive function as single formula?

There is following recursive function $$ \begin{equation} a_n= \begin{cases} -1, & \text{if}\ n = 0 \\ 1, & \text{if}\ n = 1\\ 10a_{n-1}-21a_{n-2}, & \text{if}\ ...
0
votes
2answers
20 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 ...
0
votes
0answers
28 views

Two variable recurrence relations with conditionals

Is it possible to obtain a generating function for the sequence described by the following recurrence? $$ f(n,m) = \begin{cases} f(n, \thinspace m-1) + f(n-m, \thinspace m-1), & \text{ if } n \...
0
votes
2answers
22 views

Simultaneous recurrence relations

Currently working on solving this set of three simultaneous recurrences, but having some trouble. Tried various substitutions, but still cannot seem to make any progress. Also, none of the three ...
0
votes
1answer
29 views

Solving a Linear Recurrence with a Cubic Characteristic Equation

I've been learning Linear Recurrences in my Discrete Math course and I've learned how to solve them when the characteristic equation is a quadratic. Is solving a linear recurrence with a cubic ...
0
votes
1answer
30 views

Understanding why this simple recurrence relation is structured in this manner

Given this question: Find a recurrence relation for the number of bit strings of length $n$ that contain a pair of consecutive $0$s. And this textbook answer: Let $a_n$ be the number of bit ...
1
vote
1answer
31 views

Solving linear recurrence after finding values via Quadratic Equation

My HW asks me to solve the following Linear Recurrence: $f(0) = 3 $ $f(1) = 1$ $f(n) = 4f(n − 1) + 21f(n − 2)$ Unfortunately my professor ran through the concept of Linear Recurrence ...
3
votes
2answers
37 views

Estimate growth of a recurrence convolution

Consider the following recurrence relation $$ a_{m+1} = (4 m + 1) \sum_{k=1}^m a_k a_{m-k+1}, \qquad a_1 = 1. $$ The first several values are $$ a_1 = 1,\; a_2 = 5,\; a_3 = 90, \; a_4 = 2665, \; a_5 = ...
-4
votes
0answers
61 views

Nonlinear recurrence equation $x\to(b/x)+c$ [on hold]

I have problem for solving this nonlinear recurrence equation: x_{i}=(b/x_{i-1})+c b,c are constant x_{1}=1
0
votes
3answers
68 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 ...
0
votes
0answers
11 views

How can I find runtime bounds for this recursive sum?

As part of a larger homework task, I'm investigating the following equation, given that $1 \leq s \leq n \in \mathbb{N}$ and $T_n(0) = 0$. $$ T_n(s) = \frac{1}{\lfloor \log s \rfloor} [ 1 + \log n + ...
1
vote
1answer
45 views

derivation of fibonacci log(n) time sequence

I was trying to derive following equation to compute the nth fibonacci number in O(log(n)) time. F(2n) = (2*F(n-1) + F(n)) * F(n) which i found on wiki form the ...
2
votes
1answer
27 views

Finding a recurrence for number of paths in a certain tree

I have a graph which looks like this: The question is to find a recurrence for $a_n$ - the number of paths of length $n$ that start in vertex $A$. How do you tackle these kind of problems? There is ...
0
votes
0answers
28 views

Proving $J_n(x)N_{n+1}(x)-J_{n+1}(x)N_n(x)=-\dfrac{2}{\pi x}$: Part $3$ of $3$

This is the final part of a calculation that proceeds from this previous question. Here is almost a word for word copy of the textbook question: Use the recursion relations below (for the $N_n(x)$...
1
vote
0answers
32 views

Closed form expression for a two variable recursive relation

Let $F(m,n)$ be defined recursively for non-negative integers $m$ and $n$ according to the following rules: $F(0,n) = 0$ for all $n$, $F(m,n) = F(n,m)$ for all $m$ and $n$, and if $n\ge m$, then $F(...
0
votes
1answer
46 views

Does the explicit formula for recurrence relation exist

Does an explicit formula exist for this recurrence relation? If so, what is it? $ f(0) = 1 $ $ f(n) = \frac{n}{f(n-1)} $
1
vote
1answer
24 views

# of bit strings of length n (even>2), with n/2-1 zeros and n/2+1 ones, zero followed by one

case 1: What is the number of bit strings of length 4, with 1 zero and 3 ones, zero must be followed by one Answer: 3 case 2: What is the number of bit strings of length 6, with 2 zeros and 4 ones, ...
3
votes
2answers
54 views

Prove that $\Gamma(-k+\frac{1}{2})=\frac{(-1)^k 2^k}{1\cdot 3\cdot 5\cdots(2k-1)}\sqrt{\pi}$.

I was able to prove that $$ \Gamma\left (k+\frac{1}{2} \right )=\frac{1\cdot 3\cdot 5\cdots(2k-1)}{2^k}\sqrt{\pi}.\tag{$k\geq 1$}$$ using the Legendre's duplication formula. But I can't do the same to ...
2
votes
1answer
50 views

First-Order Linear Difference Equation with Constraint

Consider the following first order linear difference equation for $y$: $$y_{t+1} = \alpha * y_{t} + \beta * x_{t-n+1} ~~\forall t \ge n$$ For initial conditions, one could assume that $x_{i} ...
1
vote
3answers
61 views

Finding a closed form for $\sum^{n}_{k=1} \frac{k}{(k+1)!} $

I'm finding a closed form to $\sum^{n}_{k=1} \frac{k}{(k+1)!} (n \leq 1) $ (in a environment of induction and recurrence) I've been trying to solve it without success, can anybody help me (?) The ...
0
votes
0answers
40 views

Solution to a first order linear difference equation

The two questions are with respect to the following first order linear difference equation $(Y_{t} - Y_{t-1}) = (1-\lambda) (X_{t-1} - Y_{t-1})$, for $t \geq n$ Also, note that the process ...
0
votes
0answers
21 views

rearranging a linear first order recurrence

Page 26 of Mathematics for Economics and Finance by M. Anthony and N. Biggs states the following equation, y' = ay' + b, and rearranges it as follows (1 - a)y' = b. I do not understand how the ...
0
votes
1answer
21 views

Proof that linear difference operator, $(σ-1)^{k+1} (p) = 0$ for all $p$ $\epsilon$ $\mathbb{Q}[t]$, with $deg(p) \leq k$.

I am trying to prove that linear difference operator, $(σ-1)^{k+1} (p) = 0$ for all $p$ $\epsilon$ $\mathbb{Q}[t]$, with $deg(p) \leq k$. In this case $\sigma(t)=t+1$ and $\sigma($anything else$)=$...
0
votes
0answers
32 views

Does this family of sequences have the limit $\left(\frac{x^{2p}-y^{2p}}{2p(\ln x-\ln y)} \right)^{1/2p}$ for $p \in \mathbb{R}$?

Define the following family of one parameter sequences: $$a_0=x,~~~b_0=y$$ $$a_{n+1}=\sqrt{a_n \sqrt[p]{\frac{a_n^p+b_n^p}{2}}},~~~b_{n+1}=\sqrt{b_n \sqrt[p]{\frac{a_n^p+b_n^p}{2}}}$$ I conjecture ...
1
vote
2answers
70 views

How do I prove the relationship between $I_n:=\int_{0}^{\pi}(\sin x)^ndx$ and $I_n=\frac{n-1}{n}I_{n-2}$ by partial Integration?

For all $n \in \mathbb{N} : n≥2$, I might add. $$I_n:=\int_{0}^{\pi}(\sin x)^ndx$$ $$I_n=\frac{n-1}{n}I_{n-2}$$ I've tried to rewrite $\int(\sin x)^ndx$ to the form $\int(\sin x)(\sin x)^{n-1}dx$ ...
-2
votes
0answers
42 views

To solve the given recursive equation [closed]

To solve the following recursive equation $$x(t+1)=\frac{(r-1)}{t} x(t) +\frac{2y(t)}{t}$$ where $y$ is some function of $t$.
3
votes
1answer
34 views

Simplifying this series of Laguerre polynomials

I trying to figure out whether a simpler form of this series exists. $$\sum_{i=0}^{n-2}\frac{L_{i+1}(-x)-L_{i}(-x)}{i+2}\left(\sum_{k=0}^{n-2-i} L_k(x)\right)$$ $L_n(x)$ is the $n$th Laguerre ...
1
vote
2answers
31 views

How do I compute the generating function for this number sequence?

I am trying to compute the generating function for the number sequence given by $a_n = (-1)^n$. I know that the solution is $A(x) = \frac{1}{1+x}$ but when I try to solve it using the procedure of ...
-2
votes
0answers
45 views

to solve the following recursive equation [closed]

How to solve the following recursive equation: $$x(t+1)=\frac{(r-1)}{t} x(t) +2P(t)x(t)$$ where $r$ is a constant lying between $0$ and $1$ and $P$ is a function of $t$, $x(t+1)$ is the value of $x$ ...
1
vote
0answers
23 views

Prove using induction that $C(n) = C(n/5) + C(3n/4) + n$ is $O(n)$

I was hoping someone could take a look at my answer to this question and check if it's correct and offer some advice/help on how to correct if it's wrong. Question: Consider the function $C: \mathbb ...
6
votes
1answer
66 views

Iterating a multiple of sine function makes a square wave

So, I found something curious playing around with a graphing calculator. Say we start with a function, $f_1(x) = 2\sin(x)$ and we define a constant, $C$,to be the positive fixed point for $f_1(x)$. ...
8
votes
2answers
243 views

Limit of the sequence $a_{n+1}=\frac{1}{2} (a_n+\sqrt{\frac{a_n^2+b_n^2}{2}})$ - can't recognize the pattern

Consider the sequence: $$a_0=x,~~~b_0=y$$ $$a_{n+1}=\frac{1}{2} \left(a_n+\sqrt{\frac{a_n^2+b_n^2}{2}} \right),~b_{n+1}=\frac{1}{2} \left(b_n+\sqrt{\frac{a_n^2+b_n^2}{2}}\right)$$ $$\lim_{n \to \...
0
votes
1answer
73 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 ...
1
vote
1answer
14 views

limiting point of a difference equation with coefficients related to a characteristic polynomial

I have a difference equation of the form \begin{equation} \mathbf{x(k+D+1)}= -(\alpha_D x(k+D)+\cdots+\alpha_1 x(k-1)+\alpha_0 x(k)) - c \end{equation} $c$ is a constant, $\alpha_D,\alpha_{D-1},\ldots,...
4
votes
2answers
76 views

The sequence $(a_n)$ is given as $a_1=1, a_{2n} = a_n - 1, a_{2n+1} = a_n + 1$. $a_{2015}=$?

The sequence $(a_n)$ is given as $a_1=1, a_{2n} = a_n - 1, a_{2n+1} = a_n + 1$. What's the value of $a_{2015}$ Correct answer should be $a_{2015} = 9$. How? thing that came to mind was to see what $...
2
votes
1answer
62 views

Prove an algorithm for logarithmic mean $\lim_{n \to \infty} a_n=\lim_{n \to \infty} b_n=\frac{a_0-b_0}{\ln a_0-\ln b_0}$

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 ...
3
votes
1answer
86 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=y$$ $$a_{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$$ ...
0
votes
0answers
49 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$
1
vote
1answer
31 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 ...
0
votes
0answers
58 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. ...
3
votes
4answers
105 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 ...
11
votes
4answers
786 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 ...
0
votes
1answer
22 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....
3
votes
2answers
30 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 ...
7
votes
3answers
269 views

How can I find an explicit expression for this recursively defined sequence?

We define the sequence $(u_n)_{n=1}^\infty$by:$$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 ...
1
vote
0answers
27 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 ...
7
votes
4answers
306 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}$$ ...
1
vote
2answers
36 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 = \...
0
votes
3answers
60 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 ...
5
votes
2answers
87 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 ...