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

learn more… | top users | synonyms (2)

2
votes
1answer
60 views

Solve recursion relation

Let $E$ be a real number. Consider the following recurrence relation: \begin{equation} a_{n+2} (n+3)(n+2) + a_{n+1} + E a_n = 0 \end{equation} subject to $a_0 = 1$ and $a_1 = -1/2$. By using the ...
0
votes
1answer
64 views

Mathematical induction

The sequence of real numbers $a_1, a_2, a_3,...$ is such that $a_1=1$ and $$a_{n+1}=\left(a_n+\frac1{a_n}\right)^\lambda,$$ where $\lambda$ is a constant greater than $1$. Prove by mathematical ...
2
votes
1answer
46 views

Recurrence relation-there is no initial condition

I want to find the exact solution of the recurrence relation: $T(n)=2T(\sqrt{n})+1$. $$m=\lg n \Rightarrow 2^m=n \\ \ \ \ \ \ \ \ \ 2^{\frac{m}{2}}=\sqrt{n}$$ So we have: ...
1
vote
3answers
20 views

Working on sequence, possibly recursive

I am working on this problem which asks to find if the sequence converges or not and if so the value it converges to. I am not sure how to deal with this type of question, but I feel like it may be a ...
31
votes
6answers
5k views

Proof the Fibonacci numbers are not a polynomial.

I was asked a while ago to prove there is no polynomial $P$ in $\mathbb R$ such that $P(i)=f_i$ for all $i\geq0$. I tried to get a proof as slick as possible and here's what I got. Let ...
4
votes
3answers
103 views

To show sequence $a_{n+1}= \frac{a_n^2+1}{2 (a_n+1)}$ is convergent

Let $a_1=0$ and $$a_{n+1}= \dfrac{a_n^2+1}{2 (a_n+1)}$$ $\forall n> 1.$ Show that sequence $a_n$ convergent. I tried to prove $a_n$ is less than 1 by looking at few terms. But i failed to prove ...
3
votes
0answers
63 views

Duration of a Gambler's Ruin game against an opponent with infinite credit

A gambler enters the casino with $x\$$ in his pocket and sits on some table. At each iteration he bets $1\$$ and either wins $1\$$ with probability $p\leq\frac{1}{2}$ or loses $1\$$. Assuming that ...
1
vote
1answer
45 views

Legendre Series Recurrence Relation Divergence at $x=\pm1$, using Gauss test

How to show that the Legendre Series solution $y_{even}$ and $y_{odd}$, diverges as $x = \pm1 $. $y_{even} = \sum_{j=0,2,\ldots}^\infty a_jx^j$, where $a_{j+2}=\frac{j(j+1)-n(n+1)}{(j+1)(j+2)}a_j$. ...
0
votes
1answer
12 views

Laguerre Recursion Relation from two other recurrence relation

How to show this, $$xL_n'(x) = nL_n(x)-nL_{n-1}(x)$$ Laguerre recursion relation from these two recursion relations, $$L'_{n+1}(x)-L'_n(x)+L_n(x)=0\\(n+1)L_{n+1}(x)-(2n+1-x)L_n(x)+nL_{n-1}(x)=0$$ ...
5
votes
1answer
111 views

What is the expected number of questions answered to complete a sequence in which wrong answers send you to the start?

Given a sequence of n questions that each contain x answer choices, what is the expected number of questions answered before answering all questions correctly if answering a question incorrectly sends ...
3
votes
1answer
47 views

Recurrence relation of number of groups of matching parenthesis

I was trying to solve this problem: How many ways can N pairs of parenthesis form K matching groups? By 'a group of matching parenthesis' I mean a sequence of matching parenthesis which can not be ...
0
votes
0answers
48 views

Find a big-O estimate for $f(n)=2f(\sqrt{n})+1$

Is the answer from the below linked question correct for my question? Or does the differing of $+ \log(n)$ instead of $+1$ change the outcome of the master theorem? Similar question here
19
votes
6answers
366 views

Why does every “fibonacci like” series converge to $\phi$?

It's is well known that the ratio of side-by-side fibonacci numbers converge to $\phi$. But it seems by my calculations, that if one starts with any pair of numbers one will also get a ratio that ...
2
votes
0answers
45 views

What techniques does Mathematica use to find solutions to these sequences?

This question is related to my previous question: Need help finding a closed form for complicated sum. An answer to that question led my to try and find the general term of the following recurrence: ...
1
vote
1answer
89 views

Asymptotic behaviour of a recurrence relation - How to solve

I'm going over a chapter in recurrence relations in preparation for job interviews and came across the following. I'd like to gain some better understanding of how to solve such a question. Find a ...
1
vote
1answer
34 views

Rewrite formula using exponential generating functions

In the equation below I want to extract $b_k$. $$\frac{a_n}{n!} = \sum_{k=0}^{n}\frac{b_k}{k!(n-k)!}$$ For all other exercises in the book I had to use $e^x = \sum_{n=0}^{\infty}\frac{x^n}{n!}$ or ...
0
votes
1answer
20 views

Recursive equation for non-recurisve equation.

Determine recursive equation for: ( $A$ is any const) $a_n = An!$ I am asking for any advice.
1
vote
2answers
31 views

System of recursive equation.

Let's consider: $$u_o = -1, v_0 = 3$$ $$\begin{cases} u_{n+1} = u_n + v_n \\ v_{n+1} = -u_n + 3v_n \end{cases}$$ I tried: $$x^n = u_n , y^n = v_n$$ $$\begin{cases} x^{n+1} = x^n + y^n \\ y^{n+1} = ...
1
vote
3answers
53 views

To prove $x_n<3$ for sequence $x_{n+1} = \frac{12(1+x_n)}{13+x_n}$ by induction

Prove $x_n<3$ for a sequence given by $$x_{n+1} = \frac{12(1+x_{n})}{13+x_{n}}$$ where $x_1$ is positive real number less than $3$. For $n = 1$ statement is trivial, but I am stuck at doing ...
1
vote
1answer
50 views

How to write $\frac{27-17x}{2x^2-x+1}$ as a series to solve this recurrence relations problem?

The relation is: $$a_n=a_{n-1}-2a_{n-2}+4^{n-2}$$ $$a_0=2, a_1=1$$ I managed to reduce the problem to the generating function: $$A(x)=\frac{2-9x+5x^2}{(1-4x)(1-x+2x^2)}$$ and then I got this: ...
3
votes
0answers
101 views

How can I convert a recursive equation to a non-recursion one? [duplicate]

While I am aware of several other similar question which have been asked in the past, my mathematical education only extends through calculus, making them beyond my comprehension, and I believe this ...
1
vote
2answers
24 views

Recurrence. Number of sequences.

Let $q_n$ be amount of sequences, where length of sequence is $n$. The sequences are constructed from elements $\in \{a,b,c,d\}$ . In sequecne 'b' occurs odd times. For example: $$n = 10$$ ...
1
vote
1answer
37 views

How to solve this multivariable recursion?

How to solve this multivariate recursion?: $$a(m, n, k) = 2a(m-1, n-1, k-1) + a(m-1, n-1, k) + a(m-1, n, k-1) + a(m, n-1, k-1)$$ where $m, n, k$ are positive integers. Edit: $a(0,0,0) = a(1,0,0) = ...
1
vote
1answer
64 views

Using induction for sequences defined by recursion, such as $a_{n+1} = \frac14(a_n^2 +3)$

Let the sequence $\{a_n\}$ be defined by $a_{n+1} = \frac14(a_n^2 +3)$. We want to prove that if the first term $a_1$ is between $0$ and $1$ then the sequence converges. My question is why do we ...
3
votes
1answer
39 views

“Multiplication” of two linear recurrence relations

Array $a_n$ is defined as: $$a_0 = 1, \quad a_{n+1} = k_{a1}a_{n} + k_{a0}$$ Array $b_n$ is defined as: $$b_0 = 1, \quad b_{n+1} = k_{b1}b_{n} + k_{b0}$$ Array $c_n$ is defined as: $$c_n = ...
1
vote
2answers
40 views

Solution for recurrence $T(n+1) = T(n) + \lfloor \sqrt{n+1}\rfloor $ [duplicate]

ould someone please give me an idea as to how the solve the following. $$T(1) = 1$$ $$T(n+1) = T(n) + \lfloor\sqrt{n+1}\rfloor$$ I converted the recurrence to $T(n) = T(n-1) + ...
1
vote
1answer
45 views

Multiples of 11 in a Fibonacci-like sequence formed by concatenation instead of addition

Let $A_1=0$ and $A_2=1$ and suppose that the number $A_n$ is obtained from the decimal expansions of $A_{n-1}$ and $A_{n-2}$. For example $A_3=A_2A_1=10$; $A_4=A_3A_2=101$; $A_5=A_4A_3=10110$. ...
0
votes
0answers
22 views

Is there a general solution to this phase-shifted system of equations?

This is a (more general) question related to "Estimated solution to system of equations with phase-shifted functions". Given this system of two equations and two unknown functions: $$ y_1(t) = ...
1
vote
1answer
26 views

Estimated solution to system of equations with phase-shifted functions

Forgive my first attempt at MathJax. I have a system of $n$ equations of the form $$ v_j(t) = \sum_{i=0}^{m-1} \frac 1 {|\vec p_i - \vec q_j|} u_i \left(t - \frac {|\vec p_i - \vec q_j|} s \right) $$ ...
-3
votes
1answer
48 views

Arithmetic Series, when $n$ tends to infinity the limit is $24$ [closed]

The $n$-th term of a sequence is $U_n$ $$U_{n+1}=pU_n+q$$ $p$ and $q$ are constants the first two terms are $U_1=96$ and $U_2=72$ the limit as $n$ tends to infinity is $24$ a) show that ...
1
vote
1answer
42 views

Discrete space and time one-dimensional walk

A person is standing on $0$ on the $x$-axis at $t=0$. After each second, the person can either move one unit to the right (with probability $a$), move one unit to the left (with probability $b$), ...
3
votes
1answer
118 views

Non-additive-subtractive prime sequence

Call the following a NON additive-subtractive prime sequence or lets name it Gary's sequence. It goes like this: let a(0)=2. The next term is defined as smallest prime number which cannot be expressed ...
0
votes
1answer
52 views

How to generalize the recurrence relation to iterative form?

I have the following recurrence relations: $$t_0=\frac{1}{a+b}+\frac{a}{a+b}\frac{1}{c}\\t_n=\frac{1}{a+b}+\frac{a}{a+b}\frac{n+1}{c}+\frac{b}{a+b}\sum_{j=1}^n p^j q^{n-j} t_{n-j}\\with\quad\quad ...
1
vote
2answers
55 views

Proving divergence of series using a recursive relation

I have been thinking for an hour about this problem but could not find any way to solve it. Let's $0\lt a_n \lt a_{n+1}+a_{n}^2$, prove that $\sum_{n=1}^{\infty}a_n$ is divergent. Any hints and ...
3
votes
0answers
37 views

Formula for numbers whose iterated distance from next square has fixed point $2$

Consider a function $R: \mathbb N \to \mathbb N,$ $R(n)$ is the distance to the next square greater or equal to $n$. For example, $R(5)=4$ and $R(16)=0.$ Function $R$ has two fixed points, $0$ and ...
0
votes
1answer
47 views

Concrete Mathematics: How do we figure out the constrains of summations when using multiplication by summation factor method?

In chapter 2.2 of Concrete Mathematics, the authors introduced the usage of summation factor to convert recurrence to summation. The idea is to multiply $s_n$ on both sides of the recurrence relation ...
1
vote
2answers
54 views

how to solve this recursive relation

please help me solve this recursive relation : $$a_n-2a_{n-1}+a_{n-2} = n-2,$$ $$ a_0 = 1, a_1 = 2, n\geq 2$$ looks like non homogenous function but I can't reach to answer.
1
vote
3answers
98 views

Recurrence Relation Involving the gamma Function

I'm having some doubts about my approach to the following problem. I am given that the function $k(z)$ is defined such that, ...
0
votes
6answers
88 views

Convergence of a sequence given by $x_{n+1}=\frac 23(x_n+1)$

A sequence $(x_n)_{n\in\mathbb N}$ is defined by $$x_0=0, \qquad x_{n+1}=\frac23(x_n+1)\text{ for }n=1,2,\dots$$ Prove that this sequence converges and find the limit. The infimum of $(x_n)$ ...
11
votes
4answers
1k views

Exponential growth of cow populations in Minecraft

Minecraft is a computer game where you can do many things including farm cows. When fed wheat, cows in Minecraft breed with each other in pairs and produce one baby per pair. After about 20 minutes ...
1
vote
1answer
25 views

Is it possible to solve the difference equation $K_{n+1}=aK_n+bK_n^{\theta}+c$?

Is it possible to solve the difference equation $K_{n+1}=aK_n+bK_n^{\theta}+c$, where a, b, c are real numbers while $\theta\in (0,1)$? How about $\theta=\frac{1}{2}$?
1
vote
0answers
24 views

Interesting recurrence equation models?

So I've had an introductory subject to recurrence equations and now I have to study a model using recurrence equations as a project. The problem is that most models I find are either elemental or ...
0
votes
1answer
43 views

If $T(n+1)=T(n)+\lfloor \sqrt{n+1}, \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?

$T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$ $T(1)=1$ The value of $T(m^2)$ for m ≥ 1 is? Clearly you cannot apply master theorem because it is not of the form ...
0
votes
0answers
28 views

What is the correct representation of Master Theorem?

What I'm taught in my class - $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$ where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number. if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$ if ...
1
vote
1answer
78 views

How to solve a recurrence relation such as $T(n) = 2T(\frac{n}{2}) +$ $\frac{n}{\log (n)}$?

Wikipedia says that the equation cannot be solved using Master's Method. The equation matches with Master's Theorem except for $\frac {n}{\log(n)}$. A youTube tutor (seek time 11:42) solves this ...
0
votes
1answer
28 views

Polynomials: functions of functions integer roots

I'm attempting to prove: Define functions $f_m$ by the recursion relation such that $f_1(x) = 2x^2-1$ and $f_k(x) = f_1(f_{k-1}(x))$ . Then for all $ m > 0$, there exists no $x \in \mathbb Z$ ...
3
votes
0answers
57 views

Relation between 2 recurrence equations. [duplicate]

I am stuck with the following recurrence relations (actually asked in a programming question).Given the following relationships, is it possible to find the index of the occurrence of any given number ...
1
vote
2answers
31 views

Solving second order difference equations with non-constant coefficients

For the difference equation $$ 2ny_{n+2}+(n^2+1)y_{n+1}-(n+1)^2y_n=0 $$ find one particular solution by guesswork and use reduction of order to deduce the general solution. So I'm happy with ...
0
votes
1answer
45 views

How to find a recursive formula for some sequence

I know how to find a non-recursive formula for a recursively defined sequence. However, now I have this puzzle which gives me a sequence (but not the recursive definition) and challenges me to find ...
0
votes
1answer
34 views

Creating equation for a given recurrence relation

I'm studying discrete math in the university, and we are given questions and answers for some problems, and I dont understand most of them. So I need help understanding one of them... Appreciate the ...