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

learn more… | top users | synonyms (2)

1
vote
0answers
17 views
0
votes
0answers
10 views

Generating function for recurrence raised to powers

Well, there are many recurrence relations as $ \displaystyle a_n^{k_n} = \sum_m {f(a_m^{k_m})}$ So, I was thinking if there is a method(a particular kind of generating functions which deals with ...
2
votes
1answer
46 views

Bibliography and references about approximations or definitions by recursion

Im curious about the topic of approximate or write some function as a recursion, i.e., the opposite to pass a recursion to a closed form or similar things. Im interested in these kind of topics ...
2
votes
0answers
22 views

fibonacci recurrence problem. [duplicate]

The Fibonacci numbers Fn are defined by the recurrence Fn=Fn−1+Fn−2, with base cases F0=0 and F1=1. Prove that any non-negative integer can be written as the sum of distinct and non-consecutive ...
1
vote
1answer
52 views

Recursion Tree method for solving Recurrences

I'm trying to find the tight upper and lower bounds for the following recurrence: T(n) = 2T(n/2) + 6T(n/3) + n^2, if n >= 3 = 1 if n <= 2 Drawing the ...
0
votes
4answers
30 views

Recursion to explicit formula

I need to try to figure out the explicit formula of the sequence $x_n=\frac{(x_{n-2}+x_{n-1})}{2}$ where $x_1=0, x_2=1$. I calculated the first few terms of the sequence and graphed it, but I'm just ...
1
vote
3answers
54 views

How to solve the non-homogeneous linear recurrence $ a_{n+1} - a_n = 2n+3 $, given that $a_0=1$?

The problem: $ a_{n+1} - a_n = 2n+3 $, given that $a_0=1$ First I solved the associated homogeneous recurrence and got $a_n = A(1)^n = A$, where A is a constant, but I got stuck solving the rest. My ...
18
votes
3answers
362 views

Recurrence relations and limits, tough.

I would like a hint for the following, more specifically, what strategy or approach should I take to prove the following? Problem: Let $P \geq 2$ be an integer. Define the recurrence $$p_n = p_{n-1} ...
1
vote
2answers
60 views

Non-homogeneous recurrence relation

For the recurrence : $$ a_{n} = 3a_{n-1} - 2a_{n-2} + F(n) $$ find the particular solution when F(n) is a) $ 2^{n} $ b) $ 2^{n}(n+1) $ c) $ 2^{n} + n+1 $ Try: I have just finished homogeneous ...
1
vote
2answers
72 views

$f(n) = 2f(n-1) -f(n-2) + 1$ find closed form by repeated substitution

$$f(0)=a$$ $$f(1)=b$$ $$f(n) = 2f(n-1) -f(n-2) + 1$$ How can I begin repeated substitution with this? I'm confused because there are two $f$ terms not sure how to sub for both of them.
1
vote
2answers
146 views

Find all polynomials $p$ such that $p(x^2)=p(x)p(x+1)$

Find all polynomials $p$ such that $$ p(x^2)=p(x)p(x+1).$$ The goal is to find a general formula for polynomials that satisfy the above equation.
2
votes
2answers
38 views

Solving recurrence relations of the form $a_{n} = b a_{n-1}^2 + c$

I have a recurrence relation of the form $a_{n} = b a_{n-1}^2 + c$, where $c \neq 0$. Specifically, mine is $a_{n} = \frac{1}{2} a_{n-1}^2 + \frac{1}{2}$, with $a_0 = \frac{1}{2}$. How are these ...
0
votes
1answer
21 views

Irreflexivity in Relations

Which relations are irreflexive? a) x + y = 0. b) x = ±y. c) x − y is a rational number. d) x = 2y. e) xy ≥ 0. f ) xy = 0. g) x = 1. h) x = 1 or y = 1. If a set is irreflexive when no ...
1
vote
1answer
24 views

How to find explicit form of recurrence relation with four variables for combinatorical value

I want to know how many ways there are to choose $l$ elements in order from a set with $d$ elements, allowing repetition, such that no element appears more than $3$ times. I've thought of the ...
2
votes
2answers
73 views

Solving recursion (Gambler's ruin)

Let $M_{i}$ denote the mean number of games until the gambler either goes broke or reaches a fortune of $N$, given that he starts with $i = 0,1,\ldots,N$. I have shown that $M_{0} = M_{N} = 0$ ...
2
votes
0answers
36 views

Recurrence Relations

...
1
vote
1answer
36 views

Counters on a Chessboard (BMO 2010/11)

Isaac has a large supply of counters, and places one in each of the $1 \times 1$ squares of an $8 \times 8$ chessboard. Each counter is either red, white, or blue. A particular pattern of colored ...
0
votes
0answers
21 views

Algorithm for finding linear recurrent approximations to integer sequences

Is there an algorithm for taking a sequence of integers and approximating a first part of it piecewise if need be with pieces like: $$ \text{ if } n = 2k, \\ a_n = a_{n-1} - a_{n-2} + 1 $$ then, ...
1
vote
1answer
33 views

recursive function: non-recursive form possible?

Can the following recursive function be converted to a non-recursive form? $$f(x,c,\ell)=\frac{c-c^\ell}{1-c}+(c-2)\sum \limits_{k=1}^{\ell-1}f(x,c,k)$$ $$f(x,c,1)=c$$ $$c= \text{constant}$$ ...
1
vote
1answer
82 views

Closed form solutions to a recursion relation

Consider a following recursion relation of degree two: \begin{equation} y_{n+1} = f_n \cdot y_n + g_n y_{n-1} \end{equation} for $n\ge 1$ subject to $y_1={\mathcal F}_1$ and $y_0={\mathcal F}_0$. By ...
1
vote
1answer
27 views

What's the general term of the squence $(U_n)_n$ such that $U_n+\frac{1}{U_{n-1}}=2$? [closed]

$$ U_n+\frac{1}{U_{n-1}}=2 $$ How we can find the general term of this sequence?
0
votes
0answers
41 views

How to solve recurrence $T(n) = T(n/3) + T(2n/3) +n$ using Master Theorem

I'm trying to solve the following recurrence using Master Theorem, but I'm not used to seeing recurrences with to terms ( i.e. T(n)) for the cost of operations. I'm pretty sure that a should be 1 and ...
1
vote
1answer
22 views

Solve the recurrence relation $a_{k+2}-6a_{k+1}+9a_k=3(2^k)+7(3^k), k\geq 0, k_0=1,k_1=4.$

Solve the recurrence relation $a_{k+2}-6a_{k+1}+9a_k=3(2^k)+7(3^k), k\geq 0, k_0=1,k_1=4.$ I know that I need a general solution of the form $a_k=a^{(h)}_k+a^{(p)}_k$, where the first term is a ...
2
votes
4answers
69 views

Finding the polynomials (or power series) $p_n(x)$ such that $2\int x^ne^{x^2}dx = p_n(x) e^{x^2}$

By using integration by parts, one can obtain the following equation $$2\int x^ne^{x^2}dx=x^{n-1}e^{x^2}-(n-1)\int x^{n-2}e^{x^2}dx .$$ A recursive formula for $\int x^ne^{x^2}dx$ that works if ...
0
votes
1answer
42 views

How to get the Delannoy Number Generating Function

The Delannoy path is a set of paths from (0, 0) to (m, n) using only steps (1, 0), (1, 1) or (0, 1). I know the generating function is $\frac{1}{1-x-y-xy}$ So far Im given, D(x, y) = $\sum_{m \geq ...
0
votes
3answers
44 views

Number of $n$-digit binary numbers such that no two zeroes are consecutive

Let $a_n$ denote the number of $n$-digit binary numbers such that no two zeroes are consecutive. Is $a_{17}=a_{16}+a_{15}$? Let $a_n$ denote the number of $n$-digit binary numbers such that no ...
4
votes
0answers
58 views

Finite sum with three binomial coefficients

I need to find a closed form expression, if there is one, of the following sum: $$\sum_{j=0}^m{n+1-k\choose j}{k-1\choose m-j}{A+2-k+m-j\choose m-j+2}$$ where all parameters are integers, $~1\leq ...
2
votes
2answers
89 views

How to show that $a_n$ : integer $a_{n+1}=\frac{1+a_na_{n-1}}{a_{n-2}}(n\geq3), a_1=a_2=a_3=1$

I would appreciate if somebody could help me with the following problem: Q: How to show that $a_n$ : integer $$a_{n+1}=\frac{1+a_na_{n-1}}{a_{n-2}}(n\geq3), a_1=a_2=a_3=1$$
0
votes
2answers
18 views

Recursion involving Piecewise

Student $C$ tries to define a function $G$: $Z^{+}\rightarrow Z$ by the rule $G$($n$) = \begin{cases} \ 1, & \text{if $n$ is 1}\\ \ G(\frac{n}{2}), & \text{if $n$ is even} \\[2ex] G(3n-2), ...
1
vote
0answers
23 views

Recurrence Solution does not satisfy base case

Can someone tell me what am i doing wrong here ? My base case i.e. T(4)=12 ...
1
vote
0answers
39 views

Analytic formulas for recursive sequences of polynomials

I have a sequence of polynomials $\{ f_{m} \}$ with $f_{m} \in \mathbb{Z}[x]$ that satisfies an order 2 linear recurrence relation. In particular, I have a polynomial $g \in \mathbb{Z}[x]$ such that ...
3
votes
0answers
63 views

Asymptotics of the solution of $G_n(t) = \text{const}$, where $G_n(t) = e^t (1 + r^{-1}(G_{n-1}(t) - 1))^{r}$.

Consider a sequence of functions $(G_n(t))$ on $\Bbb{R}$ that satisfies the recurrence relation $$ G_0(t) = e^t, \qquad G_n(t) = e^t \left( 1 + \frac{G_{s-1}(t) - 1}{r} \right)^{r}. $$ for some ...
3
votes
3answers
50 views

Solving recurrence $T(n) = T(n-2) +2 \log(n)$ using the Substitution Method

$T(n) = T(n-2) +2 \log(n)$ if n>1 & 1 if n=1 So I start by substituting 3 times to get an idea about the pattern: $T(n)=T(n-4) + 2 \log(n-2) + 2 \log n$ $T(n)=T(n-6) + 2\log(n-4) + 2\log(n-2) + ...
0
votes
1answer
104 views

Greatest Common Divisor with Fibonacci Numbers [duplicate]

Prove that for all integers $n\geq 0$: $$\gcd(F_{n+1},F_n)=1$$ I am extremely lost. Please can some provide some hint or direction? Thank you so very much
0
votes
0answers
39 views

Proving that $x_{n+1} = ax_{n}(1-x_{n})$ converges when $1<a<3$.

I need some guidance for proving $x_{n+1} = ax_{n}(1-x_{n})$ converges when $1<a<3$. What are some tips you guys could give me to help prove this point, without telling me how to do it? I'm ...
1
vote
1answer
79 views

How to show that all trajectories of the system approach a unique periodic solution?

Consider an overdamped linear oscillator forced by a square wave. The system can be nondimensionalized to $\dot{x}+x=F(t)$, where $F(t)$ is a square wave of period $T$: $F(t)=\begin{cases} +A, & ...
4
votes
4answers
98 views

Solving recurrence relation?

Consider the recurrence relation $a_1=8,a_n=6n^2+2n+a_{n−1}$. Let $a_{99}=K\times10^4$ .The value of $K$ is______ . My attempt : $a_n=6n^2+2n+a_{n−1}$ $=6n^2+2n+6(n−1)^2+2(n−1)+a_{n−2}$ ...
1
vote
1answer
42 views

Quadratic recurrence relation (from a math-contest)

It's given the following quadratic relation: $$a_n = \frac{a_{n-1}^2+61}{a_{n-2}}$$ Find $a_{10}$. Note that I can't use a calculator or a computer, instead I was wondering if there's a trick to find ...
0
votes
1answer
23 views

Initial condition for recurrence relation

I have a question regarding the solution of this problem. The problem is: Suppose that we have n dollars to use to buy either orange juice for 1, milk for 2, or beer for 2, and the order in which we ...
0
votes
0answers
49 views

consider the function $f(1) = 1$, $f(n) = \sum_{i = 1}^{n - 1}(if(i))$ for $n > 1$

Consider the function $f(1) = 1$ $f(n) = \sum_{i = 1}^{n - 1}(if(i))$ for $n > 1$ Let $A(n)$ be the worst-case number of scalar arithmetic operations (+,-,*,/) required by this function for ...
0
votes
1answer
45 views

Convert recursive formula to explicit formula using backtracking

This is a question from the book Discrete Mathematical Structures by Bernard Kolman, Robert C. Busby and Sharon Cutler Ross. I want to find the explicit formula of the following recursive formula ...
3
votes
2answers
64 views

Ramanujan's infinitely nested radical clarification

I was reading Wikipedia's article for nested radicals (link here), when I stumbled across Ramanujan's problem. I was following along fine until it got to the step where $F(x+n)$ had to be simplified. ...
35
votes
0answers
575 views

Mirror algorithm for computing $\pi$ and $e$ - does it hint on some connection between them?

Benoit Cloitre offered two 'mirror sequences', which allow to compute $\pi$ and $e$ in similar ways: $$u_{n+2}=u_{n+1}+\frac{u_n}{n}$$ $$v_{n+2}=\frac{v_{n+1}}{n}+v_{n}$$ $$u_1=v_1=0$$ ...
1
vote
2answers
49 views

Generating function to find the number of ways to put marbles in a basket

Write a generating function for the number of ways to make a basket of $n$ marbles, if you need to use at least one orange marble , an even number of yellow marbles, at most 2 green marbles, and any ...
0
votes
0answers
15 views

Inhomogeneous Legendre recurrence relation

How can I find the particular solution to following recurrence relation for $F_n(x,r)$?: $$nF_n +(2n-1)xrF_{n-1}+(n-1)r^2F_{n-2}=1$$ Withe initial values $F_0=0, F_1=1$. The corresponding ...
0
votes
6answers
91 views

Prove that the sequence: $a_1 = 1, a_{n+1} =\sqrt{c+da_n}$ (when the real numbers $c, d > 1$) is converging and find it's limit

I have a summarized solution but it's starts with proving that the sequence is bounded from above by c+d. How can I know that this sequence is bounded by c+d? I understand the proof by induction but ...
1
vote
2answers
53 views

Recurrence involving derivative

I would like to get a closed form of $A_n(x)$ if verifies the following recurrence relation $$A_n(x)=\frac{d}{dx}\left(\frac{A_{n-1}(x)}{a-\cos x}\right)\,\,\,\text{and}\,\,\,A_0(x)=1.$$ Really I ...
1
vote
0answers
30 views

Non linear recurrence from a different problem here

Referring to Non linear recurrence relation? "The recurrence (2) then implies that $ h_m=h_0+md$ for (m≥0)", What does $h_0$ refer to and how is it derived? From what I can see in equation(2), when ...
1
vote
0answers
26 views

$T(n) = 2T(\frac n 2) +\frac n {\log n}$ and the master theorem

I tried to use the master theorem to solve $T(n) = 2T(\frac n 2) +\frac n {\log n}$, and I got $\frac n {\log n} \overset{?} = O(n^{1-\epsilon})$, now it looks like it should work: $\frac n {\log n} ...
0
votes
2answers
102 views

Initial conditions that converge to an unstable equilibrium

Consider the discrete-time dynamical system \begin{align} x_{k+1}=T(x_k), \end{align} where $k\in\mathbb{N}$, $x_k\in\mathbb{R}^n$, $x_0$ is the initial condition, and $T:\mathbb{R}^n\to\mathbb{R}^n$ ...