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

learn more… | top users | synonyms (2)

1
vote
1answer
24 views

Let t(n) be the number of strings of n letters that can be produced by concatenating copies of the string “a”, “bc”, “cb” find t(3) and t(4)

For each integer n>= 1, let $t_n$ be the number of strings of n letters that can be produced by concatenating (running together) copies of the strings "a", "bc", and "cb" For example, $t_1$ = 1("a" ...
0
votes
2answers
33 views

Recursive sequence nth element formula

What is the $n$th element of this sequence: $$S_n = S_{n-1} + (c_1 - S_{n-1})c_2$$ where $c_1$ and $c_2$ are constants and $S_1=0$. Thank you,
1
vote
0answers
29 views

$a(n+1, k) = ka(n,k) + a(n,k-1)$

While working a combinatorial problem, I have encountered the recurrence relation $$a(n+1, k) = ka(n,k) + a(n,k-1)$$ where $a(0,0) = 1$ and $a(0,k)=0$ if $k \ne 0$. Except for the $k$ multiplier, ...
0
votes
1answer
12 views

Inequality in recurrence relation

I'm having a mental block understanding what is probably a simple inequality in a guess and check example for a recurrence relation. Would someone please explain to me how they obtain the inequalities ...
4
votes
2answers
45 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 ...
1
vote
0answers
27 views

How can I solve the recurrence

Solve the recurrence $f(n)=f(\frac{3n}{4})+f(n^{1-b})+cn^b$ where b and c are constants and 0 < b < 1.
2
votes
0answers
32 views

Calculate n-th term of a recursive formula

I have a sequence defined as follows: $a_1 = A$ $a_n = a_{n-1}^2 + B$ $A, B$ are positive integers. I want to design an algorithm, which would calculate $N$-th term of this recurrence modulo $10^9 ...
0
votes
1answer
23 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
34 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
63 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
49 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 ...
0
votes
2answers
31 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
466 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
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 ...
-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
473 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 ...