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

learn more… | top users | synonyms (2)

1
vote
1answer
56 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
124 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
65 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
60 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
43 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
52 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
59 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
143 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
94 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
2k 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
27 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
34 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
35 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
92 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
33 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
72 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
91 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
38 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
14 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
52 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 + ...
4
votes
2answers
56 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
58 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
27 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
130 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
90 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
49 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
55 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
50 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
22 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
21 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
23 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 ...
1
vote
2answers
45 views

two recursive sequences and the limit of their quotient

The sequences $\left \{ a_{n} \right \}$ and $\left \{ b_{n} \right \}$ are defined by the following recurrence relations: $a_{1}=b_{1}=1$ $a_{n+1}=a_{n}+2b_{n}$ $b_{n+1}=a_{n}+b_{n}$ What ...
0
votes
1answer
38 views

Simple question about recursive sequence format regarding $a(n+2) = -4a(n+1) + 5a(n)$

Suppose there's a recursive sequence $a(n+2) = -4a(n+1) + 5a(n)$ How can i convert it into the form $a(n)$ because I am most comfortable solving questions in this form. I tried to find out but I'm ...
1
vote
1answer
78 views

How to approach an equation of the form $f(x)=y$ where $f$ is recursively defined? [duplicate]

This is a homework problem so I am not looking for someone to solve it for me. I would like to know how I should approach this problem, or in what direction I should research to figure it out myself. ...
0
votes
1answer
25 views

Recurrence relation of distances between $n$-dimensional curves

I have a problem involving recurrence and euclidean distances in $n$-dimensional curves. Given the sequence of curves in $\mathbb{R}^n:$ $\{ x_{1}^2+x_{2}^2+\cdots + x_{n}^2 = 1, ...
1
vote
1answer
85 views

Finding the inverse of a recursive function?

Let's say I have this function $$f(x) = \sum_{i=0}^{x-1}f(i)$$ provided $f(0) = 0, f(1) = 1$ and $x \in \mathbb Z$. This function is evidently one-to-one on $[3, \infty) $. Is there an inverse to this ...
0
votes
4answers
53 views

How to prove the sequence given by $a_{n+1}=s+a_n^2$ is monotonic increasing?

Let $s$ be $0\:\le \:s\le \:\frac{1}{4}$ and consider this sequence: $a_1\:=\:s$ $a_{n+1}\:=\:s\:+\:a_n^2$ I want to prove that is monotonic sequence, so I thought about induction or assume in ...
2
votes
4answers
54 views

General Solution for a non-Homogeneous Recurrence

What is the general solution to the recurrence: $$x(n + 2) = x(n + 1) + x(n) + n - 1$$ where $n\geq 1$ with $x(1) = 0, x(2) = 1$? It's a question on a practice exam I'm reviewing and I'm not ...
0
votes
1answer
27 views

Stuck on a difference equation which requires an A-level method

In the non-zero sequence $x[n-1]+x[n+1]=ax[n]$ and $x[n+4]=-x[n]$ i) Find possible values of $a$. ii) For what values of $b$ is $b^n$ a solution ($x[n]=b^n$)? I need to solve this using only ...
1
vote
0answers
41 views

2nd order difference equation with n dependent coeff

I wanted to know if there was and solution to the following equation. $\left(N-n+1\right)E_{n+2} - NE_{n+1} + \left(n+1\right)E_{n} + N = 0$ Where $E_0 = 0$ and $E_1 = 2^N - 1$. $N$ is just a ...
2
votes
1answer
52 views

Number of ternary strings without consecutive zeroes

I am looking for a number of ternary strings of length n, that dont contain consecutive zeroes. This was already asked, but I am NOT looking for reccurence relation. Instead, I found this formula, ...
2
votes
1answer
51 views

Recurrence equation - floor problem

I'm having trouble solving this recurrence equation: $$x(n) = x\left(\left\lfloor \frac n2\right\rfloor \right) + n,\quad x(1)=1$$ I`m trying to find non-recurrence equation: $$x(n) = 2n - 1$$ But ...
0
votes
1answer
45 views

$\lim_{n\rightarrow \infty} a_n$ for $ a_{n+1} =a_n\cdot \frac{6+a_n}{3+2a_n}$

let there be $a_1=3$,$a_{n+1} =a_n\cdot \frac{6+a_n}{3+2a_n}$ so $a_1=3,a_2=3,etc...$ let assume there is a limit L so $L =L\cdot \frac{6+L}{3+2L}$ L=0,3 But that is not a proof, how do I continue ...
0
votes
2answers
29 views

Solving recurrence equations

Is there a method to determine the generating function for a mutually recursive recurrence equation? As an example, consider the following set if equations $$R_n = R_{n-1}+ 3P_{n-1}; R_0 = 3$$ ...
9
votes
4answers
297 views

Help with a recurrence with even and odd terms [duplicate]

I have the following recurrence that I've been pounding on: $$ a(0)=1\\ a(1)=1\\ a(2)=2\\ a(2n)=a(n)+a(n+1)+n\ \ \ (\forall n>1)\\ a(2n+1)=a(n)+a(n-1)+1\ \ \ (\forall n\ge 1) $$ I don't have much ...
1
vote
0answers
82 views

$T(n) = T(n/2 - \log(n)) +1$ using Substitution Method

I have the following recurrence: $$T(n) = T(n/2 - \log(n)) +1$$ How can this be solved using the substitution method? I don't fully understand the theory of this method and I'm not sure how to apply ...
0
votes
1answer
49 views

Express recurrence in closed form

I am having trouble understanding the process of expressing the following recurrence in its' closed form. First of all, I do not really understand what "closed form" means. If someone could elaborate ...