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

learn more… | top users | synonyms (2)

1
vote
0answers
20 views

Frobenius Method

We have been given a Hermite equation $ \frac{d^2 y}{dx^2} -2x \frac{dy}{dx}+2ny=0$ We need to use the Frobenius method to solve. So far we have solved the indicial equation and got r = 0,1 and the ...
0
votes
1answer
44 views

Properties of Bessel Functions

I have shown that the Bessel function $$J_n\left(x\right)=\dfrac{x^n}{2^n}\sum^{\infty}_{n=0}\dfrac{\left(-1\right)^kx^{2k}}{2^{2k}k!\left(n+k\right)!}$$ satisfies the property $$\left(x^{n+1}J_{n+1}...
1
vote
1answer
27 views

Where does this reccurence relation come from?

if$$\alpha_m = \int^{1}_{-1}\cos \pi x (x^2-1)^m dx$$ then how do I get $$\alpha_m = \frac{-1}{\pi^2}(2m(2m-1)\alpha_{m-1} + 4m(m-1)\alpha_{m-2})$$ I have to integrate by parts! But $$\alpha_n = -\...
0
votes
1answer
31 views

Find the Bessel Function solution of the differential equation

For positive n, the ordinary differential equation $$y''+\dfrac{1}{x}y'+\left(1-\dfrac{n^2}{x^2}\right)y=0$$ has as a solution the Bessel function of order n, $J_n\left(x\right)=x^n\sum^{\infty}_{k=...
0
votes
1answer
29 views

Find a recurrence relation and the Fourier-Legendre Series

Rodrique's Formula for the $n$th Legendre Polynomial is $$P_n\left(x\right)=\dfrac{1}{2^nn!}\dfrac{d^n}{dx^n}\left(\left(x^2-1\right)^n\right)$$ The Fourier-Legendre series of a function f is ...
1
vote
1answer
76 views

Given $x_m=4x_{m-1}-x_{m-2},\ x_1=1,\ x_2=3$

I friend told me that apart from trivial ones, the elements in this sequence never equal powers of 3: $$x_m=4x_{m-1}-x_{m-2},\ x_1=1,\ x_2=3.$$ Could you please help me to prove this?
18
votes
1answer
258 views

Repeatedly taking mean values of non-empty subsets of a set: $2,\,3,\,5,\,15,\,875,\,…$

Consider the following iterative process. We start with a 2-element set $S_0=\{0,1\}$. At $n^{\text{th}}$ step $(n\ge1)$ we take all non-empty subsets of $S_{n-1}$, then for each subset compute the ...
1
vote
1answer
39 views

Deducing Skolem-Mahler-Lech theorem from a $p$-adic interpolation result.

Let $p$ be a prime number, let $d$ be an integer greater than $1$ and let $f\in\mathbb{Z}_p[X_1,\cdots,X_d]^d$. I have already proved the following $p$-adic interpolation theorem: Theorem 1. (...
0
votes
3answers
20 views

General and particular solution from recurrence equation

I need to find the General Solution of $S_n = 3S_{n-1}-10$ for n = 1,2,3,4.... then I need to find the particular solution where $S_0 = 15$, then check the particular solution with the original ...
0
votes
2answers
36 views

How to find limit of the sequence

A sequence is defined by recurrence relation $f_{n+1}=\frac{3}{7}f_n+8$ with $\mu_0=-14$, then what is the limit of the sequence? $14$ $-14$ $\frac{-3}{7}$ $\frac{3}{7}$ My attempt: As wiki : ...
1
vote
0answers
44 views

asymptotic behavior of functions which are defined recursively

For $x\in[0,1]$, define $f_1(x)=1$ and $$ f_{n+1}(x)=(1-x)^n\left(nx+1\right)+f_n(x)\left(1-(1-x)^{n+1}\right)\;\;\mbox{for}\;\;n=1,2,\dots. $$ I want to study some asymptotic results of $f_n$. For ...
17
votes
3answers
221 views

Fibonorial of a fractional or complex argument

Let $F(n)$ denote the $n^{\text{th}}$ Fibonacci number$^{[1]}$$\!^{[2]}$$\!^{[3]}$. The Fibonacci numbers have a natural generalization to an analytic function of a complex argument: $$F(z)=\left(\phi^...
1
vote
1answer
30 views

How to solve master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$

Im trying to solve this using master theorem $T(n) = 3T\left(\frac{n}{2}\right) + \frac{n^2}{\log_2 n}$ but I dont know how. So far we know that $a=3$, $b=2$, $f(n) = \frac{n^2}{\log_2 n}$. Which ...
-1
votes
1answer
78 views

Is there a sequence of positive integers such that $a_{n+3}-a_{n+2}=\sqrt{a_{n+1}+a_n}$? [closed]

Can anyone give me a hint on this? Is there a sequence of positive integers such that $(a_{n+3}-a_{n+2})^2=a_{n+1}+a_n$ for all $n$? Or strongly, $a_{n+3}-a_{n+2}=\sqrt{a_{n+1}+a_n}$. If there is, ...
1
vote
0answers
109 views

Are there bounded nonconvergent sequences satisfying this recurrence relation?

In this question, we ask about convergent sequences $(p_n)$ satisfying $p_{i} = 2p_{i+6} - {1 \over 2}p_{i+1} - {1 \over 4}p_{i+3} - {1 \over 8}p_{i+7} - {1 \over 16}p_{i+15} - {1 \over 32}p_{i+31} - ...
2
votes
1answer
109 views

Bessel's Differential Equation - textbook queries:

In order to ask this question I must first give some background information as written in my text book: Given Bessel's Differential equation: $$x^2y^{\prime\prime}+xy^{\prime}+(x^2-p^2)y=0$$ ...
0
votes
1answer
26 views

Particular Solution of Recurrence Equation

Given: $S_{n+2} = 13S_{n+1} + 48S_n$ for $\forall n \in N$ I've found the General Solution which is $S_n = A16^n - B3^n$ I don't quite understand how to find the particular solution where $S_0 = 1$ ...
2
votes
3answers
32 views

General Solution and Particular Solution of Recurrence Equation

I am given: $S_{n+2} = S_{n+1}+S_{n} + {2}$ for $\forall n \in N$ My question is how do I find the general solution of the recurrence equation. And the particular solution where $S_0=1$ and $S_1 = ...
0
votes
2answers
33 views

recurrence relation number of bacteria

Assume that growth in a bacterial population has the following properties: At the beginning of every hour, two new bacteria are formed for each bacteria that lived in the previous hour. During the ...
0
votes
1answer
23 views

How do I solve this first order difference equation?

I have the difference equation: $x(n+1) = \beta + x(n)(1-\alpha - \beta)$, where $\alpha, \beta$ are constants, with initial condition $x(0) = 1$. The solution says that the answer is $$x(n) = \...
1
vote
1answer
46 views

Master theorem with $f(n) = n\log(\log n)$

I have a question related to algorithm time complexity and master theorem. How to solve this master theorem $T(n) = 2T(n/2) + n\cdot \log(\log(n))$? We have 3 cases: I don't know which one to ...
1
vote
0answers
19 views

Determining the E.G.F from an Umbral Type Recurrence Formula

Suppose I have the recurrence formula $$\left(A+\frac{2}{3}\right)^n+w_3^2\left(A+\frac{1+w_3}{3}\right)^n+w_3\left(A+\frac{1+w_3^2}{3}\right)^n=0; A_0=1, A_1=-\frac{1}{3}$$ where $w_3=\exp(2i\pi/3)....
7
votes
2answers
473 views

Recurrent sequence limit

Let $a_n$ be a sequence defined: $a_1=3; a_{n+1}=a_n^2-2$ We must find the limit: $$\lim_{n\to\infty}\frac{a_n}{a_1a_2...a_{n-1}}$$ My attempt The sequence is increasing and does not have an upper ...
5
votes
1answer
79 views

If $s(1)=1$ and $s(n)=s(n-1)+\text{lcm}[n,s(n-1)]-(-1)^n$ then $\lim\limits_{n\to \infty}\frac{s(n)}{(n+1)!}=\frac{1}{e}$

Define the sequence $(s(n))$ recursively by $s(1)=1$ and, for every $n\ge2$, $$s(n)=s(n-1)+\text{lcm}[n,s(n-1)]-(-1)^n.$$ Prove that $$\lim_{n\to \infty}\frac{s(n)}{(n+1)!}=\frac{1}{e}$$ I got ...
0
votes
0answers
16 views

Stuck: To show that the divide and conquer relation represent Merge Sort

I've just started with recurrence relations. I know that the divide and conquer relation in merge sort is given by, $M(n) = 2M(n/2) + n$ Question: A divide and conquer relation is given $$a_n = ...
0
votes
1answer
44 views

Good number $n=a_1+a_2+a_3+\cdots+a_k$ with $ {1\over {a_1}} + {1\over {a_2}} + {1\over {a_3}} + \cdots+{1\over{a_k}}=1$

An integer n will be called good if we can write $n=a_1+a_2+a_3+\cdots+a_k$, where $a_1,a_2,a_3 \ldots a_k$ are positive integers (not necessarily distinct) satisfying: $$ {1\over {a_1}} + {1\over {...
0
votes
0answers
58 views

How to find the first 5 values of a recursive relation where certain sequences are not known?

Write down the first five values of each of the following recursive sequences. (a) r(0) = 2, r(n) = [r(n-1)] -n -1 for all integers n>=1 (I couldn't write the values as ace of r and s so I just wrote ...
0
votes
0answers
14 views

Solve the reccurence $T(n) = 3T(\sqrt[3]{n}) + log_{2}(log_{2}n)$

$T(1) = 1 $ , $T(n) = 3T(\sqrt[3]{n}) + log_{2}(log_{2}n)$. I tried to define $ n = 2^{k}$. So, $T(2^k) = 3T(2^{\frac{k}{3}}) + log_{2}k$ Then defin $S(k) = T(2^k)$ So ,$S(k) = 3S(\frac{k}{...
-2
votes
1answer
37 views

Recurrence relation general solutions [closed]

how would I go about tackling this kind of question? I'm struggling with the concept of recurrence relations. Any advice would be apreciated. Find the general solution of each of the following ...
0
votes
1answer
17 views

Subsets of an ordered round table of numbers

The problem reads: Let the integers $1,2,\dots,n$ be arranged consecutively around a circle, and let $g(n)$ be the number of ways of choosing a subset, no two consecutive on the circle. In a ...
0
votes
1answer
63 views

Recurrence relation problems

For some math homework (that was already due but I really want to understand the content) I was asked the following question, How should I go about answering this? I'm new to recurrence relations and ...
2
votes
1answer
43 views

Radius of convergence from recurrence with variable coefficients

I am solving via power series the ivp $$y'-2xy=0,\quad y(1)=2.$$ The "solution" is $$y(x)=2\left(1+2(x-1)+3(x-1)^2+\frac{10}{3}(x-1)^3+\frac{19}{6}(x-1)^4+\frac{26}{10}(x-1)^5+\cdots\right)$$ with ...
1
vote
0answers
37 views

12 numbered pigeonholes and balls [duplicate]

This problem was inspired by this James Randi challenge. Given $12$ numbered ($1$ to $12$) pigeonholes and $12$ numbered balls (also from $1$ to $12$); what is the probability that a random ...
0
votes
0answers
13 views

Difference equation of Z-Transform

I could not obtain difference equation of Z-Transform which is indicated below: $$H(z) = \frac {1.1202\cdot10^{-6}z^2 + 2.2404\cdot10^{-6}z + 1.1202\cdot 10^{-6}}{z^2 -1.9996z + 0.996}$$ In simple ...
15
votes
4answers
914 views

How does one solve this recurrence relation? [closed]

We have the following recursive system: $$ \begin{cases} & a_{n+1}=-2a_n -4b_n\\ & b_{n+1}=4a_n +6b_n\\ & a_0=1, b_0=0 \end{cases} $$ and the 2005 mid-exam wants me to calculate answer ...
0
votes
2answers
32 views

Proving a sequence defined by a recurrence relation converges

How can I prove that this iterative sequence converges to $2$? Can I use the convergence definition? $$a_{n+1} = \frac{a_n}{2} + \frac{2}{a_n},\qquad a_0 = 4 $$ Thanks for the help.
0
votes
2answers
17 views

Finding a general form $d_n$ for a recurrence relation

I have the following recurrence relation $$d_n = 2^{(1-2n)/2}d_{n-1},\qquad d_0=1,$$ for $n\in\mathbb{Z}$. Is it possible to find a general form for $n$? After calculating a few numbers around ...
0
votes
0answers
22 views

best way to find sum of powers of prime factors of a number

What is the best way to find the sum of powers of prime factors of a number? What I did till now is : ...
0
votes
2answers
53 views

Solution to recurrence relation, as a formula involving summation operator

Here is what I am tasked with.. Find a solution to the recurrence relation: $F(0) = 2$ $F(n+1) = F(n) + 2n^2 - 1$ as a formula involving the summation operator $$\sum_{i=1}^n$$ Sorry for the ...
0
votes
1answer
38 views

Solving the recurrence $ T[n] = \frac{n}{T[n-1]}$

Ive had some experience solving recurrences but i think they have been more simple than this one. This is what i have so far: \begin{array}{rcl}T[1] & = & 1 \\ T[n] & = & \frac{n}{T[...
1
vote
2answers
15 views

Alternative Derivation of Recurrence Relation for Bessel Functions of the First Kind

How can the recurrence relation $J^{'}_n(x) = \frac{1}{2} [J_{n-1}(x) - J_{n+1}(x)]$ be derived directly from the following? $J_n(x) = \frac{1}{\pi} \int_0^\pi \cos(n\theta - x \sin\theta) \text{d} ...
-2
votes
1answer
27 views

Periodicity of solutions of rational difference equations $x_{n+1}=\alpha+\frac{x_{n-1}}{x_n}$ [closed]

\begin{equation*}x_{n+1}=\alpha+\frac{x_{n-1}}{x_n}\tag{1}\end{equation*} Equation(1) has solutions of prime period 2 if and only if $\alpha = 1$. How to prove this? Thanks.
0
votes
0answers
27 views

Solving a recurrence relation using a subtitution method $T(n+1)=T(\frac {n} {2} )+ \Theta\left(n^2 \right) $

I got stuck when I want to solve this recursive relations by substitution $$ T(n+1)=T(\frac {n} {2} )+ \Theta\left(n^2 \right) . $$ $$ T(n+1)=2 T(\frac {n} {2} )+ \Theta\left(n\right) . $$ $$ T(n)=T(\...
1
vote
1answer
27 views

Solution to a 2D recurrence equation

I am seeking an explicit solution to this 2D recurrence equation: \begin{eqnarray} f(0,b) & = & b\\ f(a,0) & = & a\\ f(a,b) & = & f(a-1,b) - f(a,b-1) \end{eqnarray} So, for ...
2
votes
1answer
26 views

unfolding of a recurrence

I've been reading the book "Concrete Mathematics" from Graham et. al. And there is a relation (on pg. 27) $s_n = s_{n-1}a_{n-1}/b_n$, and authors point that this relation can be unfolded, resulting ...
2
votes
1answer
27 views

How to rearrange this doubly infinite sum for a diffeomorphism using the existence of a first integral?

Let's take two diffeomorphisms $F,G: \mathbb{R}^{n} \mapsto \mathbb{R}^{n}$. Let $x \in \mathbb{R}^{n}$, and $x^{n} = F^{n}(x)$, where $n \in \mathbb{Z}$. Suppose that $F$ has a first integral, i.e. ...
6
votes
5answers
171 views

Convergence of a recurrence

Given the recursive definition (starting with a positive integer) $$ a_n = \frac{a_{n-1}}{2}+4 $$ I am trying to find an explicit form and show that it approaches 8. So I started by writing it out, ...
0
votes
1answer
17 views

How to solve the recurrence relation

I was going through a problem on combinatorics and came up with the recurrence relation like this. These equations hold for all natural values of $n$. ($p_n$ is the final result that I want) $$p_n=...
28
votes
2answers
428 views

Find $\sqrt{4+\sqrt[3]{4+\sqrt[4]{4+\sqrt[5]{4+…}}}}$

Find the value of $$\sqrt{4+\sqrt[3]{4+\sqrt[4]{4+\sqrt[5]{4+...}}}}$$ I know how to solve when all surds are of the same order, but what if they are different? Technically, (as some users wanted ...
0
votes
0answers
26 views

Finding a shorter recursive equation

The assignment is the following: (a) Given a sequence $(a_n)_n$ which satisfies the recursive equation $a_n = \sum\limits_{k = 1}^d c_k \cdot a_{n-k}$ with $c_d \not= 0$. Furthermore $Q = 1 - c_1t - \...