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

learn more… | top users | synonyms (2)

1
vote
1answer
88 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
36 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
38 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
44 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
41 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
51 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
54 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
52 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
87 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
42 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
77 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
28 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 ...
1
vote
1answer
12 views

Looking for a recurrence relation ot combinatorial way to calculate initial number

A flock of birds migrating south flies above seven lakes. Half of the birds in the flock, plus half a bird(I'm guessing the initial flock contained an odd number of birds, say 5, so in the first lake ...
0
votes
2answers
39 views

Solve the recurrence relation (using iteration?)

$a_n = a_{n-1} + 1 + 2^{n-1}\\ a_0 = 0$ Not sure how to iterate with the exponent term. Here's what I got: $= (a_{n-2} + 1 + 2^{n-1}) + 1 + 2^{n-1} = a_{n-2} + 2 + 2(2^{n-1})\\ = (a_{n-3} + 1 + ...
3
votes
2answers
46 views

How to solve linear, second order ODE with Frobenius method with a difficult recurrence relation?

The ODE in question is: $$4xy''+2y'+y=0$$ Shifting the power series of each term so that they are all raised to the power $(n+r)$ will yield this recurrence relation: $$a_{n+1}={a_n\over ...
2
votes
1answer
50 views

Understanding Generating Function

I have been looking at This Problem and Answer about generating functions. The problem asked for the generating function of: $$a_n=4a_{n-1}-4a_{n-2}+{n\choose 2}2^n+1$$ I understand how Ron Gordon ...
0
votes
1answer
25 views

Recurrence relation advice

$t_n=5t_{n-1}+6t_{n-2}$ Is the characteristic equation of this correct? This is what I have: $x$- 5$x$ -6=0 Is this correct?
1
vote
3answers
38 views

Finding a closed-form formula for a sequence that is defined recursively

$$a_0 = 0, a_1 = 1 \quad \text{ and } \quad a_n = a_{n-1} + 2a_{n-2}\quad \text{ for }n\geq 2$$ a) Find $a_2,a_3,a_4,a_5$ b) Find a closed form-formula for $a_n$ I found the value to be ...
2
votes
1answer
78 views

Solve the recurrence relation: $2a_n = 7a_{n-1} - 3a_{n-2}; a_0 = a_1 = 1$

$2a_n = 7a_{n-1} - 3a_{n-2}\\ a_0 = a_1 = 1$ My attempt: $2t^2 - 7t + 3 = 0\\ t = -\frac{1}{2}, -3\\ \\ U_n = b(-\frac{1}{2})^n + d(-3)^n\\ b+d = 1 = -\frac{1}{2}b-3d\\ b = \frac{8}{5}, d = ...
0
votes
1answer
46 views

Solve the Recurrence

Solve the recurrence $a_k = 2a_{k-1} + 3a_{k-2}$, if $a_0 = 0$ and $a_1 = 8$. I understand how to get the generating function: $$G(x) = \sum_{k \geq0}a_kx^k = a_0 + a_1x + \sum_{k\geq 0}a_kx^k = 8x ...
1
vote
2answers
51 views

Solve the recurrence $a_{n+2}=5a_{n+1}-9a_n+3n$?

What is the simplest way to solve the recurrence $a_{n+2}=5a_{n+1}-9a_n+3n$, with the initial values $a_0=2,a_1=1$? Is it possible to do this with generating functions?
1
vote
1answer
33 views

Recurrence relation stuck on partial fraction decomposition

I am stuck in trying to solve the following recurrence relation: $$S_n = rS_{n-1} + nrB$$ where $r$ and $B$ are constants. To solve this I made the following generating function: $$f(x) = ...
1
vote
0answers
15 views

Asymptotic Notations Iterative Method for Solving Recurrences

Recurrence T(n)= T(n^1\2) + O(lg(lg(n))) The solution suggests substituting m = lg(n) So the recurrence becomes S(m)= S(m\2) + O(lg(lg(m))) Then solving using iterative method for solvng ...
0
votes
1answer
20 views

Part of a proof recurrence relation

I'm reading this survey by Carl Offner about digit computation of the number $\pi$. In page 7 there's a step that I didn't understand: suppose $$\alpha_{n+1}=\frac{\alpha_n \beta_n}{\alpha_n + ...
0
votes
2answers
17 views

Solving a single-term recurrence relation with a variable coefficient?

$a_n = 2na_{n-1}\\ a_0 = 1$ How do I solve this? Is there a characteristic equation? I found $a_1 = 2, a_2 = 8, a_3 = 48$ but I don't know what to do with that information to solve. Please help, ...
0
votes
0answers
16 views

Solving single term recurrence relation?

$a_n = -3a_{n-1}\\ a_0 = 2$ Therefore $a_1 = -3(2) = -6\\ a_2 = -3(-6) = 18\\ a_3 = -3(18) = 54$ So... $x^n = -3^{n-1}$? If so $x^2 = -3^1$, so $x^2 + 3 = 0$, then $x = \pm (i\sqrt3)$. That doesn't ...