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

learn more… | top users | synonyms (2)

2
votes
3answers
40 views

The sequence $a_{n}a_{n+1}=a_{n+2}$

The product of two corresponding terms in a sequence $a_n$ determines the next term. Find the general solution. My approach: $$x^{b+c}=x^bx^c$$ Let $b=F_n$ and $c=F_{n+1}$ then the sum ...
0
votes
1answer
26 views

Solving recurrence equation that appear in biology

I am struggling to solve this recurrence equation, $$a_{n}(1-sa_{n-1}^{2})+sa_{n-1}^2-a_{n-1}=0$$ where the parameter $s\in[0,1]$ and the initial condition $a_{0} > 0$ is close to 1. I have ...
1
vote
1answer
31 views

Limit of $13^{a_n}=12^{a_{n-1}}+5^{a_{n-2}}$

I have the following recurrence: $$13^{a_n}=12^{a_{n-1}}+5^{a_{n-2}},\;a_0=0,\;a_1=1.$$ I have to prove that it is monotone and bounded, and I have to find the limit as $n\to\infty$. It was for an ...
2
votes
0answers
27 views

Need reference for fact about roots of characteristic polynomials of recurrences

Many famous sequences $\{a_n\}$ satisfy recurrence relations. For example, the Fibonacci numbers $\{0,1,1,2,3,5,\ldots\}$ and Lucas numbers $\{2,1,3,4,7,11,\ldots\}$ both satisfy $$ a_n = a_{n-1} + ...
-2
votes
1answer
45 views

Let $a_1 = 2$ and for all natural number n, define $a_{n+1}= a_{n}(a_{n}+1)$. Then as $n\rightarrow \infty$, the number of prime factors of $a_{n}$ [closed]

Let $a_1 = 2$ and for all natural number n, define $a_{n+1}= a_{n}(a_{n}+1)$. Then as $n\rightarrow \infty$, the number of prime factors of $a_{n}$: goes to infinity. goes to a finite limit. ...
0
votes
0answers
47 views

Recurrence for the Mertens function generalized to complex numbers.

It is well known that the sum of the Möbius function $\mu(n)$ over divisors is zero unless $n=1$. $$\sum\limits_{d|n} \mu(d) = \delta_{n \, 1}$$ where $$\delta_{n \, 1}$$ is Kronecker delta. Or put ...
5
votes
2answers
183 views
0
votes
1answer
19 views

Is this a valid base case?

I'm trying to prove this for all $n \geq 1$. Using the recursive formula, I ended up with this: $F_{-(n+1)} = F_{-n} - F_{-(n+2)}$. If the formula holds for $n$ and $n+2$, I can eventually turn the ...
3
votes
0answers
50 views

Count number of m-subsets with xor = 0 [closed]

Given positive integers $n$ and $m$, count the $m$-subsets $S\subseteq[2^n - 1]$ such that the bitwise XOR of the members of $S$ is $0$, where as usual for any positive integer $k$ we let ...
2
votes
0answers
41 views

Fundamental theorem of arithmetic, prove that these matrices are the same apart from the main diagonal.

I know and I can prove that the fundamental theorem of arithmetic is encoded uniquely by this recurrence written in Mathematica 8: ...
4
votes
2answers
49 views

Simplify the series given by the recurrence relation $na_n=2a_{n-2}$

If you are given a recurrence relation such that: $$na_n=2a_{n-2}\implies a_n= \begin{cases} 0 & \text{odd} \,n \\ \frac{2}{n}a_{n-2} & \text{even} \,n \end{cases}$$ My textbook suggests ...
5
votes
1answer
74 views

Reference request for an identity involving binomial coefficients

The identity is $$\sum_{i\ge 0}(-1)^i \binom{\frac{s^k + s^{-k} - 10}{4}}{i}\binom{\frac{s^k + s^{-k} - 10}{4}+4}{\frac{gs^k + 2g^{-1}s^{-k} - 4}{8}-i}= 0$$ where $k\gt 1$ , $s = 3+2\sqrt{2}$ ...
2
votes
2answers
48 views

Prove that largest root of $Q_k(x)$ is greater than that of $Q_j(x)$ for $k>j$.

Consider the recurrence relation: $P_0=1$ $P_1=x$ $P_n(x)=xP_{n-1}-P_{n-2}$; 1). What is closed form of $P_n$? 2). Let $k,j.\in\{1,2,...,n+1\}$ and $Q_k(x)=xP_{2n+1}-P_{k-1}.P_{2n+1-k}$. Then ...
0
votes
1answer
15 views

Recurrence Relation for QuickSort

Suppose a special recurrence relation for quicksort is: $T(0)=\Theta(1)$ (N>0) $T(N)= T(N-1)+T(0)+\Theta(\sqrt{N}) $ How does this relate to the theta class of: $\Theta(N \sqrt{N})$ ? Can someone ...
3
votes
2answers
62 views

How show that $a_{n}=n$ if $ a_{n+1}+a_{n-1}=\frac{2n}{a_{n}-a_{n-1}}$

define sequence $\{a_{n}\}$ such $a_{1}=1,a_{2}=2$, and such $$ a_{n+1}+a_{n-1}=\dfrac{2n}{a_{n}-a_{n-1}},n\ge 2$$ show that:$$a_{n}=n$$ I want use without induction solve this sequence?
2
votes
2answers
80 views

A square root solving algorithm invented by my friend

Recently, my friend told me a square root algorithm: $$ \left\{ \begin{array}{lll} p_{n+1}&=&p_n+aq_n \\ q_{n+1}&=&p_n+q_n\end{array}\right.$$ Finally, $p_n/q_n$ is near $\sqrt{a}$. ...
3
votes
1answer
52 views

Compute $\sum\limits_{n=1}^{\infty} \frac1{1+x_n}$ if $x_1>0$ and $ x_{n+1} = x_n ^2 + x_n $

Suppose $ x_1\in \Re $ , and let $ x_{n+1} = x_n ^2 + x_n $ for $ n\geq 1 $. Assuming $ x_1 > 0 $, find $ \sum_{n=1}^{\infty} 1/(1+x_n) $. What can you say about the cases where $ x_1 < 0 $? ...
0
votes
1answer
25 views

How to derive the general solution of a recurrence relation?

I know for a recurrence relation $$X(n)=c_1X(n-1)+c_2X(n-2).....+c_kX(n-k)$$ the characteristic equation is $$X^n=c_1X^{n-1}+c_2X^{n-2}+...$$ I know the general solution if all roots are equal is ...
0
votes
0answers
15 views

recurrence algorithm unfolding with answer, need explanation

SO the question is to prove $O(n\log n)$ hence figure out $f(n)$ correct? why does $n = 2^{2^k}$ what is so special about $2^{2^k}$ can i use another number? this answer is using substitution? I ...
1
vote
0answers
29 views

Expected sum of picked numbers from set

Let suppose that I have a finite set $X$ of natural numbers. I keep drawing, with reintroduction and uniform probability, from this set until the sum of the extracted numbers, $S$, is bigger or equal ...
3
votes
2answers
25 views

Solve the recurrence relation $a_n = 2a_{n-1} + 2^n$ with $a_0 = 1$ using generating functions

Here is what I have so far, or what I know how to do, rather: I am given this equation: $a_n = 2a_{n-1} + 2^n$ with $a_0 = 1$ So, with the $2a_{n-1}$, I know I can do the following. We change the ...
1
vote
0answers
48 views

Complexity of recurrence equation 6

$B(n)=B(⌈ n/\log_2 n⌉)+\theta(n)$ B(2)=1 Here is my attempt: \begin{align*} B(n) &= 3B(\lceil n/\log_2 n\rceil) + \Theta(n)\\ &= 3\big(3B(\lceil n/(\log_2 n)^2\rceil) + \Theta(n)\big) + ...
1
vote
3answers
30 views

Solve the linear recurrence with initial conditions $a_n=a_{n-1}+2^n+1$ and $ a_0 =0$

Let $(a_n)_{n\geq0}$ be the sequence defined by $$a_0=0\qquad\text{and}\qquad\forall n\geq0,\ a_n=a_{n-1}+2^n+1.$$ I know this is a non-homogeneous case and so far as I have gotten the general ...
1
vote
1answer
29 views

To find the Generating function for the given case

$$a_{n} = \frac{4^{3n-5}}{3^{2n+4}}$$ I was just able to reach till $a_{n}$ = ($\frac{64}{9}$) $a_{n-1}$ Don't know how to proceed further
3
votes
1answer
33 views

To calculate generating function

If $a_{n}$ = $\frac {1}{(n-1)(n+1)}$ for $n\ge2$ What are we supposed to do with $a_{0}$ and $a_{1}$? How can I find the generating function without using $a_{0}$ and $a_{1}$?
3
votes
2answers
65 views

How fast does this sequence grow?

I have the following recursive definition of a sequence of numbers: $$a_{n+1}=(a_n)^{(a_{n-1})}$$ And $a_0=a_1=2$. The first few terms are: $$a_2=4$$ $$a_3=16$$ $$a_4=65536$$ $$a_5=1.1579209 ...
5
votes
2answers
77 views

show that $2^k|n\Longleftrightarrow 2^k|a_{n}$

Let sequence $\{a_{n}\}$ such $a_{0}=0,a_{1}=1,a_{n}=2a_{n-1}+a_{n-2}$. show that $$2^k|n\Longleftrightarrow 2^k|a_{n}$$ I try to find the $\{a_{n}\}$ closed form ...
1
vote
4answers
55 views

Recurrence relation involving matrices

I've done part $(i)-(iv) [(i) (C), (ii) (D),(iii) (F), (iv) (E)].$ I would appreciate if someone could show me how to solve this part (v).
2
votes
1answer
28 views

Proving $T(n) = T(n-2) + \log_2 n$ to be $\Omega(n\log_2 n)$

As title, for this recursive function $T(n) = T(n-2) + \log_2 n$, I worked out how to prove that it belongs to $O(n\log n)$; however I'm having trouble proving it to be also $\Omega(n\log n)$, i.e. ...
0
votes
0answers
14 views

On Hyper-geometric function differential equation

The hypergeometric function $$_2F_1(a,b;c+n:z) = \sum_{m=0}^\infty \frac{(a)_m(b)_m}{(c+n)_m}\frac{z^m}{m!}$$ should satisfy the differential equation $$z(1-z)\frac{d^2u}{dz^2} + ...
0
votes
0answers
24 views

On Hyper-geometric Functions and its recurrence relation

I research in generating functions of Hyper-geometric functions $_2F_1(a+n,b;c+n;x)$ using Lie group theoretic method and so the recurrence relation is important in this method. I want recurrence ...
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
45 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
53 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
361 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} ...
2
votes
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
144 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
72 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
20 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}$$ ...