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

learn more… | top users | synonyms

1
vote
2answers
129 views

$a_{n+1}=\frac{1}{2}\left(a_n+\frac{1}{a_n}\right)(n=1,2,3,\cdots),~a_1=2$

I would appreciate if somebody could help me with the following problem: Q: find $a_n=?$ $$a_{n+1}=\frac{1}{2}\left(a_n+\frac{1}{a_n}\right)(n=1,2,3,\cdots),~a_1=2$$
5
votes
2answers
286 views

Whats better: 1 million dollars in a month or a penny(USD) doubled (and added) every day for 30 days?

THis is a question that I remember when I was in the 5th grade that tested our logical reasoning skills. And it is a simple choice knowing that the pennies doubling every day is an exponential ...
10
votes
1answer
190 views

Solve $A_n=A_{n-1}+\lfloor \sqrt{A_{n-1}}\rfloor$

I am trying to solve the recurrence: $A_0=1$ $A_n=A_{n-1}+\lfloor \sqrt{A_{n-1}}\rfloor,\text{ for } n > 0$ Its obvious that $A_n=m^2 \implies A_{n+1}=m^2+m$ however my book's solution states ...
13
votes
5answers
417 views

Solve the sequence : $u_n = 1-(\frac{u_1}{n} + \frac{u_2}{n-1} + \ldots + \frac{u_{n-1}}{2})$

For a physical model I am trying to solve this sequence: $$\begin{align*} u_1 &= 1 \\ u_2 &= 1-\left(\frac{u_1}{2}\right) \\ u_3 &= 1-\left(\frac{u_1}{3} + \frac{u_2}{2}\right) \\ u_4 ...
2
votes
1answer
187 views

A recurrence relation on two variables

How to solve the recurrence relation for $n >=m$: $$P_{n,m}=\frac{n}{n+m}P_{n-1, m} + \frac{m}{m+n}P_{n,m-1}$$ $$P_{11}=\frac{1}{2}; P_{i,0}=1 \forall i > 0; P_{i,j}=0 \forall i<j$$
1
vote
1answer
207 views

Program, Recurrence relation, Master-Theorem

Programming code: t(n) { for i=1 to n sum=sum+1 if (n>1) sum=sum+t(n/2)+t(n/2) return sum } I built the ...
5
votes
2answers
310 views

A Recurrence Relation Involving a Square Root

Consider the recurrence relation: $a_{n+1} = \sqrt{a_n^2 -k},$ where $k>0$, $n\in\{0,1,n:a_n^2\geq k\}$, and $a_0>0$ is known. Is it possible to obtain an expression for $a_n$ in terms of ...
2
votes
2answers
107 views

Asymptotic bound $T(n)=T(n/3+\lg n)+1$

How would I go about finding the upper and lower bounds of $T(n)=T(n/3+\lg(n))+1$?
0
votes
1answer
97 views

find the recurrence relation of a string

So I got this problem: compute the number of n bit string that do not contain pattern 010 that have no leading 0, one leading zero, two leading zero, and so on. So far, I got the expression: ...
3
votes
2answers
106 views

Solve recurrence formula

Thanks! That helps a lot. I think the substituting is the way to go
0
votes
1answer
156 views

Solving the following recurrence relation

I have a recurrence relation, it is like the following: $$ T(e^n) = 2\cdot T(e^{n-1}) + e^n, \text{ where $e$ is the natural logarithm} $$ To solve this and find a Θ bound, i tried the following: I ...
1
vote
2answers
93 views

The use of master theorem appriopriately

I have a recurrence relation and trying to use master theorem to solve it. The recurrene relation is: $$T(n) = 3T\left(\tfrac n5\right) + \sqrt n$$ Can i use the master theorem in that relation? If ...
4
votes
3answers
138 views

Need help about solving a recurrence relation

I have a recurrence relation which is like the following: $$ T(n) = 2T(n/2) + \log_2 n. $$ I am using recursion tree method to solve this. And at the end, i came up with the following equation: $$ ...
0
votes
1answer
58 views

Is this recurrence relation correct?

from here Consider the sequence $5, 0, -8, -17, -25, -30, \dots$ given by the recursion shown. $$a_0 = 5 \\ a_n = a_{n - 1} + n^2 - 6$$ Is this correct? I can calculate $a_1$: $$a_1 = 5 + 1^2 - ...
2
votes
0answers
102 views

Is there a closed form for this recurrence?

Given $$ E_{n,k} = \begin{cases} 0 & \text{ if } n \leq k \\ n & \text{ if } k = 0 \\ \sum_{i=0}^{n-1} \dfrac{1}{n} \cdot E_{i,k-1} & \text{ otherwise } \end{cases} $$ I wonder is there ...
6
votes
5answers
201 views

How can I find the value of $a^n+b^n$, given the value of $a+b$, $ab$, and $n$?

I have been given the value of $a+b$ , $ab$ and $n$. I've to calculate the value of $a^n+b^n$. How can I do it? I would like to find out a general solution. Because the value of $n$ , $a+b$ and $ab$ ...
6
votes
2answers
354 views

unorthodox solution of a special case of the master theorem

I am asking for references regarding a special case of the master theorem. This theorem seems to appear quite a lot on this site, prompting me to study it in more detail, e.g. see my posts here and ...
0
votes
1answer
57 views

Identifying a pattern in an array

Is there a way to identifying a pattern and/or recursive function for an array? If yes, how can I do this. Could anyone please help me with some information and/or resource for this? Any help is ...
1
vote
2answers
825 views

Solving a recurrence relation using master method

I know that the Master theorem is used for the recurrence relations of the form: $$T(n) = aT(n/b) + f(n)$$ In my question, I am supposed to solve the following recurrence relation by using Master ...
2
votes
1answer
320 views

recurrence-relation via master theorem

This is homework assignment on proving algorithm time complexity using Master Theorem. I have been trying to solve it for several hours by now with no luck. Can someone please at least explain, what ...
1
vote
2answers
200 views

Finding the asymptotic behavior of the recurrence $T(n)=4T(\frac{n}{2})+n^2$ by using substitution method

I am trying to solve a recurrence by using substitution method. The recurrence relation is: $$T(n)=4T\left(\frac{n}{2}\right)+n^2$$ My guess is $T(n)$ is $\Theta (n\log n)$ (and I am sure about it ...
4
votes
2answers
267 views

Sum of the series formula

I need to figure out the sum of the series as quickly as possible in a program given n and k: $$f(n,k)= ...
0
votes
2answers
112 views

$T(n) = T (\frac{n}{5}) + \frac {n}{\log (n)}$ Solving

I want to find the bound for $T(n) = T (\frac{n}{5}) + \frac {n}{\log (n)}$. I tried with forward iteration and this is what i 've got $T(1) = c$ $T(5^1) = c + 5^1$ $T(5^2) = c + 5^1 + (5^2)/2$ ...
2
votes
3answers
66 views

generating functions, can't seem to get the correct answers.

So, I've been having some issues with generating functions and counting problems. An example problem is: $$ a_n = a_{n-1} + 9a_{n-2} - 9a_{n-3} \;\;\; (n \geq 3)$$ Where $a_0 = 0, a_1 = 1, a_2 = 2$ ...
6
votes
5answers
149 views

$x_{n+1} = \sqrt{3x_n}$ converges for $x_1 = 1,x_1 = 27$ Proof

Prove $x_{n+1} = \sqrt{3x_n}$ converges for $x_1 = 1,x_1 = 27$. (Separate problems for $x_1 = 1$ and $x_1 = 27$.) EDIT: Took out bad algebra.
1
vote
1answer
22 views

Square terrain recurrence derivation

You have a square terrain with area $A > 0$. You want to add information into the terrain. You want to subdivide the terrain into $4$ quadrants, process them individually, and assemble the results. ...
1
vote
2answers
82 views

Solving a recurrence relation

I have a recurrence relation that I would like to solve. $T(n)$ belongs to $\Theta(f(n))$. $T(n) = 2T(\frac{n}{4}) + c$, where $c$ is a constant. The base case, $T(1)$ is a constant as well. My ...
2
votes
1answer
79 views

Constant term of recursively defined polynomials related to the Lambert W function

The Lambert $W$ function has the property that $$ W'(x) = \frac{W(x)}{x[1+W(x)]}, $$ and using this one can show that its Taylor expansion about $x=a$ has the form $$ W(x) = W(a) + ...
1
vote
3answers
125 views

How to solve two recurrences dependent on each other

Let $F_n = a_1*F_{n-1} + b_1*F_{n-2} + c_1*G_{n-3}$ $G_n = a_2*G_{n-1} + b_2*G_{n-2} + c_2*F_{n-3}$ We are given $ a_1,b_1,c_1,a_2,b_2,c_2$ and $ F_0,F_1,F_2, G_0, G_1,G_2 $. We have to calculate ...
0
votes
4answers
410 views

Having a lot of trouble solving this recurrence with iteration and finding a closed form…

I'm learning discrete math and didn't have any trouble with any recurrences in the examples I went over through the chapters on it, but this one problem at the end of the first chapter is killing me, ...
0
votes
0answers
65 views

proving an inequality by induction

Not sure how to proceed. I'm trying to prove that the following inequality is true. I know that $t_2 = 6$ and $t_3=17$ from the problem statement. The base case is obvious. $t_{r+1} \leq (r+1) (t_r ...
1
vote
2answers
34 views

Solving a recurrence based on the solution to another.

I have a solution to a recurrence $g(n)=f(n) + g(n-1)$, and I'd like to solve the recurrence $h(n) = \alpha[f(n) + h(n-1)]$. I guessed the solution was $h(n) = \alpha^ng(n)$, but it turns out this ...
0
votes
2answers
45 views

Recursive equations critical boundary

I have an interesting problem and i don't have any idea about how to solve it :-) I'm given a system of $K$ equations (with $N \gt K$ , and $0 \lt f \lt 1$) $$f(1-f)^{K-1} - (1-f)^{N-K} \alpha_K = ...
12
votes
3answers
280 views

How to find a “better description” (e.g. recurrence relation) for this sequence?

My solution to a problem in Project Euler required to solve this subproblem: find values of $k\in\mathrm{N}$ such that $3k^2+4$ is a perfect square. As I was writing a computer program, I just tried ...
0
votes
1answer
252 views

Recurrence relation using the master theorem $ T(n) = 4T(n/2) + n^2 \log n$

I am trying to solve the following recurrence relation using the master theorem: $ T(n) = 4T(n/2) + n^2 \log n$ So: $a=4 ,b=2, f(n)=n^2\log n$ , then $n^{\log_2 4}=n^2 $ Now i know that $n^2 \log n ...
0
votes
2answers
196 views

Recursive combinatorics with numbers and operators

I have the following question that I have difficulty to grasp: A string from 0,1,+,-,*,/ There are 2 rules: 1) string must start and end with a number. 2) string must not have two operators one after ...
1
vote
1answer
95 views

Prove If $a_0=2, a_{n}=\frac{\pi^{n+1}}{n!}\int_{0}^{1}t^n(1-t)^n\sin( \pi t)dt(n\geq 1)$ then $a_{n+1}+a_{n-1}=\frac{4n+2}{\pi}a_n $

I would appreciate if somebody could help me with the following problem: Please explain how to do this proof ? $$$$ If $$a_0=2, a_{n}=\frac{\pi^{n+1}}{n!}\int_{0}^{1}t^n(1-t)^n\sin( \pi t)dt(n\geq ...
1
vote
1answer
77 views

Prove by Induction $\frac{a_n-\sqrt{A}}{a_n+\sqrt{A}} = \left[\frac{a_1-\sqrt{A}}{a_1+\sqrt{A}}\right]^{2^{n-1}} $

$a_1=\frac{1}{2}(a_0+\frac{A}{a_0})$; $a_2=\frac{1}{2}(a_1+\frac{A}{a_1})$; and $a_{n+1}=\frac{1}{2}(a_n+\frac{A}{a_n})$ for $n \geq 2$; where $a\gt 0$, $A\gt 0$. Prove: ...
0
votes
2answers
54 views

If $ i=0.09 $, find $ n $ and the amount of final payment.

A fund of $ \$500 $ is to be accumulated by $ n $ annual payments of $ \$100 $, plus a final payment as small as possible made one year after the last regular payment. If $ i = 0.09 $, find $ n $ and ...
4
votes
5answers
312 views

What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$,$F(1)=b$ and $a,b>0$?

What is closed-form expression for $F(n)$ when $F(n)=F(n-1)+F(n-2)$ and $F(0)=a$, $F(1)=b$ and $a,b>0$ ? It seems to be simple generalization of Fibonacci sequence but I can't find closed form for ...
1
vote
1answer
72 views

Explicit formula for recurrence relation with $A_{N+1}= A_N+{(2/7)}^N$

How can I find a non-recursive formula for the sequence $A_N$ when the sequence is defined as $A_1=1$ and for $N\ge 1$, $A_{N+1}= A_N+{(2/7)}^N$?
3
votes
1answer
75 views

Solving the recurrence: $h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 $

I want to solve the following recurrence: \begin{equation} h(1) = 0\\ h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1 \end{equation} What are some basic "methods" I can use to guess a ...
3
votes
1answer
41 views

Is there a general formula for recurrence relations like $ f(x+1) = \sum_{i=0}^k a_n{[f(x)]}^n $

Or in other words, polynomial relation of the function rather than the argument. I've worked out that in general $ f(x+1)={f(x)}^n $ implies $$f(x) = C^{n^x} $$ for some C, but I would like to know if ...
4
votes
1answer
116 views

Give a combinatorial proof of the recurrence relation

Let $F_n$ be the number of forests on the vertex set $V = \{1,2,\ldots,n\}$(Thus we are counting labelled forests). Give a combinatorial proof of the recurrence relation $$F_n = \sum_{i=1} ...
3
votes
2answers
123 views

Systems of recurrence relations

This is homework, please only provide hints! I have a question: Given a 1-by-n board, let $a_{n}$ denote the number of ways to color the board with red, blue, white and green where that the number of ...
2
votes
1answer
565 views

Concrete Mathematics - The Josephus Problem

I've been going through Concrete Mathematics and have a question on the inductive proof for the Josephus problem. Recurrent relation: $J(1) = 1$ $J(2n) = 2J(n) - 1$ $J(2n+1) = 2J(n) + ...
2
votes
1answer
113 views

Show that Fermat number $F_n$ and its index $n$ are coprime.

I want to show that $\gcd(F_n,n)=1$, where $F_n=2^{2^n}+1$. How to prove this? I can show that that $\gcd(F_n, F_m)=1$ for any natural $n$ and $m$, and that $F_{n+1}=(F_n)^2-2F_n+2=F_0\dots ...
1
vote
2answers
102 views

What is the asymptotical bound of this recurrence relation?

I have the recurrence relation, with two initial conditions $$T(n) = T(n-1) + T(n-2) + O(1)$$ $$T(0) = 1, \qquad T(1) = 1$$ With the help of Wolfram Alpha, I managed to get the result of ...
3
votes
0answers
102 views

How to resolve this equation for f(n) without using f(n-1)

I have an equation related to some work I'm doing on Poisson distribution where I'm calculating a sequence of 100 values between a minimum and maximum value which is set by another formula. ...
3
votes
1answer
162 views

Issue while applying Master Theorem

I've read about the master theorem for solving recurrences in Introduction to Algorithms, but have a problem (probably, due to misunderstanding) while applying it in some cases. For example, having ...