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

learn more… | top users | synonyms (2)

1
vote
1answer
55 views

Proof by Induction that if $s_1 < s_2$ and $s_{n+1} = \frac{s_{n+1} + s_n}{2}$ then $s_1 < s_n < s_3$ for all $n \ge 3$

Suppose$$s_1 < s_2$$ Use induction to show if $$s_{n+1} = \frac{s_{n+1}+s_{n}}{2}$$ for all $$n \geq 1$$ then: $$s_1< s_n < s_2, \ n \geq 3$$ I have no idea how to do this. I tried ...
3
votes
2answers
122 views

Argument over an induction proof

My friend gave me a problem. Define a sequence $\langle a_n \rangle$ by the recurrence relation :$$ a_{n+2} - 6a_{n+1} + 8a_n = 0 $$ and $a_1 = 4, a_2 = 8 $. Find the general term $a_n$ in ...
2
votes
1answer
57 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: ...
1
vote
3answers
351 views

Show that the greatest common divisor of any two terms in recursive sequence $T_{n+1} = T_n^2 - T_n + 1$ is 1.

Question: Consider the sequence of integers $T_n$ , where $n ∈ N$ defined by the recurrence relation $T_0 = 2$ , $T_{n+1} = T_n^2 - T_n + 1$ (for $n ∈ N$). Show that for any $m$ , $n ∈ N$ ...
1
vote
1answer
39 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) $$ ...
1
vote
1answer
103 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
2answers
25 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
81 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 ...
0
votes
4answers
116 views

How do I prove convergence of the recursive sequence $c_n = c_{n-1} + \frac{0.01}{n}$?

I have this sequence: $c_n = c_{n-1} + \frac{0.01}{n}, \ \ c_1 = 0.01$ How do I prove the convergence of this, and what is the limit? Context I was trying to solve the problem of a snail crawling ...
1
vote
2answers
45 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
60 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
24 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) = ...
-3
votes
1answer
84 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
2answers
65 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 ...
0
votes
1answer
83 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 ...
3
votes
0answers
49 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 ...
1
vote
1answer
101 views

Recurrence relation for Binary String Question

I have a question which has been a little stumped. I'm pretty sure I know the answer, but don't know how to prove it to be true. Here it is: "Given an infinite length random binary string, what is ...
1
vote
2answers
63 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.
3
votes
4answers
284 views

Solving Recurrence equation

I have a problem with this type of recurrence equation. Find the solution of recurrence equation: $$T(1)=2,$$ $$T(n+1)=T(n)+2n , \quad \forall n\geq 1$$ Indeed, I tired to Solving Recurrences ...
6
votes
5answers
129 views

Recurrence of the form $2f(n) = f(n+1)+f(n-1)+3$

Can anyone suggest a shortcut to solving recurrences of the form, for example: $2f(n) = f(n+1)+f(n-1)+3$, with $f(1)=f(-1)=0$ Sure, the homogenous solution can be solved by looking at the ...
1
vote
3answers
224 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, ...
10
votes
1answer
1k views

How to solve non-linear recurrence relation in general?

For linear recurrence, we can use generating function. So is there a general technique to solve non-linear recurrence or it depends on a specific sequence? For example, $$a_{n+1} = \dfrac{a_n(a_n - ...
1
vote
6answers
100 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)$ ...
1
vote
2answers
50 views

Relation between series and equations

There is following quotes from wiki on Plastic number: The powers of the plastic number $A(n) = ρ^n$ satisfy the recurrence relation $A(n) = A(n − 2) + A(n − 3)$ for $n > 2$. And 2nd is that ...
2
votes
1answer
88 views

Find $a_{n}$ from a convolution formula

Suppose that $c_{n}$ satisfies the recurrence formula below: $c_2=\alpha$, and $$c_{2n}+c_{2n-2}=\frac{(\alpha)_n}{n!},n\geq2.$$ were $(\alpha)_n = \alpha(\alpha-1)·\cdots·(\alpha-n+1)$ and $\alpha$ ...
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
29 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}$?
2
votes
2answers
102 views

Find $a_{2012}-3a_{2010}/3 a_{2011}$ where the sequence $a_n$ is determined by roots of a quadratic equation

If $\alpha$ and $\beta$ are the roots of $x^2-9x-3=0$, $a_n=\alpha^n-\beta^n$ and $b_n=\alpha^n+\beta^n$, then find the value of $\dfrac{a_{2012}-3a_{2010}}{3 a_{2011}}$ and ...
1
vote
0answers
36 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 ...
1
vote
1answer
129 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 ...
7
votes
1answer
262 views

Compute limit of the sequence $x_n$ given by $x_{n+2}=-\frac{1}{2}(x_{n+1}-x_n^2)^2+x_n^4$

Let $(x_n)$ be a real sequence such that $x_0=a\in\mathbb{R},x_1=b\in\mathbb{R},x_{n+2}=-\dfrac{1}{2}\left(x_{n+1}-x_{n}^2\right)^2+x_{n}^4\;\forall n\in\mathbb{N} $ and $|x_n|\leq ...
4
votes
0answers
58 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 ...
0
votes
1answer
38 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$ ...
0
votes
1answer
2k views

Implementing discrete Poisson equation wtih Neumann boundary condition

I understand how to implement a discrete 2D poisson solution with Dirchlet boundary conditions. Using http://en.wikipedia.org/wiki/Discrete_Poisson_equation#On_a_two-dimensional_rectangular_grid , you ...
0
votes
1answer
168 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
46 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
17 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
58 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 + ...
2
votes
1answer
113 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
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?
5
votes
2answers
122 views

Proving a solution to a double recurrence is exhaustive

The equation $$ b^2 = \frac{a(a+1)}{2} + 1 $$ where $a$ and $b$ are integers, has the following smallish-integer solutions: ...
1
vote
2answers
56 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?
0
votes
1answer
57 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 ...
0
votes
1answer
103 views

Solve the recurrence relation $x_{n+2} -3x_{n+1} + 2 x_n = n$

Solve $$x_{n+2} -3x_{n+1} + 2 x_n = n$$ when $x_0 = 1$ and $x_1 = 0$. I started with the homogen solution: $$r^2 -3r +2 = 0$$ So $$x_n^h = A1^n + B2^n$$ I know that $x_n = x_n^p + x_n^h$ But I ...
1
vote
1answer
73 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
33 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
29 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
21 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 ...