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

learn more… | top users | synonyms (2)

4
votes
2answers
30 views

Show that the sequence $x_n=\Big[\frac32x_{n+1}\Big]$, $x_1=2$ contains an infinite set of odd numbers and an infinite set of even numbers.

I am having a hard time proving this Let $x_n$ be a sequence such that $x_{n+1}=\Big[\frac32x_n\Big]$ for $n\gt1$, where $[x]$ denotes the nearest integer function and $x_1=2$. Show that ...
0
votes
1answer
21 views

Solving differential equations using series

Suppose $v \in \mathbb{R}$ and $$y\left(x\right)=x^v\left(1+\sum^{\infty}_{n=1}a_nx^n\right)$$ where the series converges for any $x \in \left(-r,r\right), r>0$ If $y\left(x\right)$ is a solution ...
1
vote
0answers
13 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
32 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 ...
0
votes
1answer
29 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, ...
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 ...
7
votes
1answer
78 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
26 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
0answers
58 views
+100

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} - ...
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
75 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?
2
votes
1answer
81 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$$ ...
1
vote
0answers
16 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
19 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 ...
-2
votes
0answers
28 views
5
votes
1answer
47 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: ...
-1
votes
1answer
32 views

Need to find the recurrence equation for coloring a 1×n board with no specific sequence aoccure [on hold]

Let $a_n$ be the number of ways to to color the square $1 \times n$ board using the colors red, white, and blue, So that specific sequence red-white-blue does not occur. i have 2 cases case 1 if ...
1
vote
2answers
29 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
39 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 ...
0
votes
2answers
31 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 ...
2
votes
2answers
59 views

Intersection of two recurrences.

I have two sequences obtained by recurrences: $$f(0) = 1, f(1) = 9, f(n+2) = 10f(n+1) - f(n)$$ $$g(0) = 1, g(1) = 7, g(n+2) = 6g(n+1) - g(n)$$ How can I prove that apart from $f(0) = g(0) = 1$, these ...
4
votes
3answers
2k views

Notation for factorial-type pattern with a skip/step of two instead of one?

I came across a peculiar pattern when solving a recurrence relation today: Some sequence $a_n$ looks as such: $a_0 = 1$ $a_2 = \frac{1}{2 \cdot 1}$ $a_4 = \frac{1}{4 \cdot 2 \cdot 1}$ $a_6 = ...
-1
votes
1answer
77 views

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

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, ...
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
1answer
21 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) = ...
7
votes
2answers
464 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 ...
1
vote
2answers
65 views

How can I prove if these are (or not) possible solutions for the following recurrence?

So I'm presented with no initial conditions and the following recurrence relation: $8a_{n+2}+4a_{n+1}-4a_n=0$ I need to determine if these are possible solutions, and in that case, which initial ...
1
vote
1answer
44 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
18 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 ...
5
votes
1answer
74 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 ...
7
votes
0answers
71 views

Finding a recurrence relation for a sequence not containing $0$ in the digits. Also showing $\sum\limits_{k=1}^n \dfrac{1}{a_k} < 90$

Let $1,2,3,4,5,6,7,8,9,11,12,\ldots$ be the sequence of all positive integers which do not contain the digit zero. Write $\{a_n\}$ for this sequence. By comparing with a geometric series, show that ...
0
votes
2answers
37 views

Prove boundedness of recurrence relation

For a number sequence $\{y_n\}$ we know that $y_{n+1} = 2y_n-y^2_n$ If: $0<y_0<1$ show that $0<y_n<1$ for all integers $n>0$ I've tried solving the recurrence relation, but I couldn't ...
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
57 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 ...
-2
votes
1answer
12 views

Finding a general solution to homonogeneous and nonhomogenious reccurence [closed]

How would I go about solving the following questions, I'm really struggling with the concepts and would love to have some insight. Thanks.
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) = ...
-2
votes
1answer
31 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 ...
-1
votes
0answers
37 views

Explanation of a recurrence relation

for (iv) why do we have $2 U_{(n-1)} +8U_{(n-2)}$?? I thought $U_n = 2U_{(n-1)} + 9U_{(n-2)}$? Thanks :)
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 ...
2
votes
1answer
39 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 ...
2
votes
3answers
468 views

How to find formula for recursive sequence sum?

I have the following sequence: $$a(1) = 1$$ $$a(n) = a(n-1) + n$$ For example: $$a(1) = 1$$ $$a(2) =3$$ $$a(3) =6$$ $$a(4) =10$$ $$a(5) =15$$ $$a(6) = 21$$ Which approach should I use in order to ...
0
votes
1answer
60 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 ...
14
votes
4answers
892 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 ...
1
vote
0answers
35 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 ...
0
votes
2answers
29 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.
11
votes
1answer
259 views

Mathematics of the Ice Bucket Challenge

I've been considering the mathematics of the now global ice bucket challenge. Simple model In the simplest incarnation, there is one original seed, who then nominates 3 others, each of which take ...
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. ...