1
vote
1answer
12 views

Identifying R1 and R2 when solving Recursion relations

We are learning to solve recursion relations. When I get this step, does it matter if I define $r_1$ as 5 or 2 in this example?
2
votes
1answer
65 views

Solving the recursion $y_n=2ny_{n-1}$ with Wolfram|Alpha

This is blowing my mind away ... this should be easy stuff! Starting with the recursive formula $y_n=2n*y_{n-1}$ where $y_1=5.$ I'm trying to come up with a formula for the series { 5, 20, 120, 960, ...
2
votes
1answer
29 views

Recurrence relation of the following sequence?

This is the code: for (unsigned int i = 0; i < n; ++i) if (i % 2 == 0) ++k; And this is the output for when ...
1
vote
1answer
35 views

How do I create a function from this code? [closed]

Here is the code: for (int i = 1; i < n; i *= 2) ++k; I need to express this as a function. I don't know where to begin.
0
votes
1answer
27 views

Why does the sign change here?

They give the recurrence relation as: $$T(n) − 4T(n − 1) + 3T(n − 2) = 0,\ T(0) = 0,\ T(1) = 2$$ And then they say it can be written as the following for $n > 1$: $$T(n) = 4T(n − 1) − 3T(n − 2)\ ...
1
vote
2answers
36 views

Help with proof by induction

The author generates a Tower of Hanoi and looks at the sequence: $$1, 3, 7, 15, 31, 63,...$$ He guesses the recurrence relation from the first few terms: $$H_{n} = 2^{n} - 1$$ Now he wants to ...
1
vote
2answers
72 views

How does this simplification work?

The following recursive function was given: $$T\left(n\right) = T\left(n - 1\right) + x$$ The author stated that by using repeated substitution we can solve the recurrence relation: The basic ...
0
votes
1answer
46 views

On the existence/applications of infinitely-nested functions

Inside a previous question, one particular nested function shown is the known tetration. This "kind" of arbitrary repeated functions has always intrigued me, because inside their properties lie so ...
2
votes
1answer
24 views

Clarification regarding the Josephus problem in Concrete Mathematics (Knuth, et al)

In page 9 of Concrete Mathematics, regarding the Josephus Problem, they state that "each person's number has been doubled then decreased by 1". $J(2n) = 2J(n) - 1$, for $n \ge 1$ I don't quite ...
1
vote
1answer
43 views

Evaluation of a Hankel-like determinant

I consider the following determinant (Hankel-like?) $$ [f_1,f_2,...,f_n]:=\begin{vmatrix} f_1 & f_2 & \cdots & f_{n-1} & f_n\\ n-1 & f_1 & \cdots & f_{n-2}& f_{n-1}\\ 0 ...
3
votes
1answer
37 views

What's the time complexity of T(n)=nlogn+T(n-1)?

The title says it all. The best I can come up with is that this expands to T(0) + 1log 1 + 2log 2 + ... + (n-1)log (n - 1) + nlog n which is ...
1
vote
2answers
40 views

Recurrence with multiplication

Let $\{a_{n}\}$ be a sequence of nonnegative numbers such that $a_{n} = 2^{n}a_{n - 1}^{3/2}$. If $a_{1}$ is sufficiently small, why must $a_{n} \rightarrow 0$ as $n \rightarrow \infty$?
1
vote
2answers
44 views

Find a recurrence for in , the number of integer compositions of n which only have 1s and 2s as parts.

Find a recurrence for $$i_n$$ the number of integer compositions of $n$ which only have $1$s and $2$s as parts. How do you approach this problem?
1
vote
2answers
66 views

How to solve this mathematically

This is a question given in my computer science class. We are given a global variable $5$. Then we are to use keyboard event handlers to do the following: On event keydown double the variable and on ...
0
votes
1answer
73 views

Solving this recursive function $f(x)=f(x-k)+f(x/k)$.

How to solve or simplify the following recursive function? $f(x)$ is defined only for whole numbers as follows: $$f(x)=\begin{cases} 1 & \mbox{if } x<k; \\ f(x-k)+f(x/k) ...
0
votes
1answer
42 views

recurrence relation question.

I have this expression: $I_{n} = \int_0^1 \frac{x^{n-1}}{2-x} dx$ for $n=1,2,3,\ldots$ I have been asked to show that by writing $x^n = x^{n-1} (2-(2-x))$ that the recurrence relation $I_{n+1} = 2I_n ...
-1
votes
1answer
57 views

I am not how they got characteristic equation from the given equation.

![can someone tell me they got characteristic equation from the given recursive equation.][1] i know how to do the rest of problem but getting characteristic equation stopped me. The recurrence is ...
2
votes
3answers
77 views

Solving Recurring Relations

Can you please help, my son has been trying for over two hours now to solve the following: A sequence of terms $\left\{u_n\right\}$ is defined for $n\geq 1$, by the recurrence relation: ...
2
votes
1answer
68 views

An inequality property of the Fibonacci sequence

Given the Fibonacci sequence $F_n$, Wikipedia says (http://en.wikipedia.org/wiki/Fibonacci_number#List_of_Fibonacci_numbers) $$ F_{2n-1} = F_n^2+F^2 _{n-1}$$ so that $$F_{2n-1}>F^2_n$$ What is the ...
1
vote
1answer
40 views

Simplifying a Recurrence Relation

$(n_i) $ is a sequence of integers satisfying $n_{i+1}=a_{i+1}n_i+n_{i-2}$. Consider a subsequence $(n_{i_j}).$ Can $n_{j_{i+1}}$ be written in terms of $n_{j_i}$? An attempt is to use the recurrence ...
0
votes
3answers
84 views

Recurrence relation of two next terms

For the recurrence relation, $a_{n+2}=3a_{n+1}-2a_n$ with $a_0=2$ and $a_1=3$, compute the first six terms of the sequence and derive a closed form formula for this sequence. So I'm totally lost with ...
1
vote
1answer
127 views

Alternative solutions to $n^2+n = k^2+k + 2kn$

Consider this equation: $n^2+n = k^2+k + 2kn$ I want to find the set of non-negative integer n,k that satisfies the equation. I tried to write $n$ as $k$ by solving the equation with $n$ as root ...
1
vote
1answer
226 views

Establishing formula from recurrence

Can anyone tell me how do we establish a formula from a given recurrence relation? Take the example of $f(n) = 2f(n-1) + 1$, $n \in \mathbb{Z^+}$, $f(1) = 1$ When I write out the first few values, it ...
20
votes
4answers
508 views

Evaluating $\sqrt{1 + \sqrt{2 + \sqrt{4 + \sqrt{8 + \ldots}}}}$

Inspired by Ramanujan's problem and solution of $\sqrt{1 + 2\sqrt{1 + 3\sqrt{1 + \ldots}}}$, I decided to attempt evaluating the infinite radical $$ \sqrt{1 + \sqrt{2 + \sqrt{4 + \sqrt{8 + \ldots}}}} ...
0
votes
1answer
166 views

Convert a recurrence relationship into an algebraic equation

I have a piece of code that describes a recursive relationship to produce a logarithmic sweep: ...
1
vote
0answers
100 views

How to find the recurrence polynomial?

Problem: If $f$ is a polynomial with unknown roots $x_1,-x_1,x_2,-x_2\ldots,x_b,-x_b \quad (b \in \mathbb{N})$ and can be expressed as (known expansion): $$f(x)=\sum_{a=0}^{2b}f_ax^a\quad(b \in ...
0
votes
2answers
505 views

Using recurrences to solve $3a^2=2b^2+1$

Is it possible to solve the equation $3a^2=2b^2+1$ for positive, integral $a$ and $b$ using recurrences?I am sure it is, as Arthur Engel in his Problem Solving Strategies has stated that as a method, ...
3
votes
1answer
255 views

Non-linear recurrence problem

How to convert $p_n$ to an expression in terms of $n$ if $3p_{n-1}^2 - p_{n-2}=p_{n}$ and $p_0=5, p_1=7$? This is a problem I haven't been able to finish for two days, please help. This question ...
1
vote
1answer
147 views

Question about generating function in an article

Could someone explain what $R(x)$ and constant $c_1,c_2,...,c_k$ are in this article about characteristic polynomial in proof 3? If that someone could rephrase it, because it seems not so clear in ...
0
votes
1answer
86 views

Can we express $p_n$ in terms of $p_0, p_1$ and $n$?

$p_0=a$, $p_1=b$, $bp_n=p_{n+1}+p_{n-1}$ express $p_n$ in terms of $a,b,n$. Any help would be appreciated, because you guys are splendid.
0
votes
1answer
808 views

Rearranging a general closed form linear recurrence sequence

I have the following general closed form linear recurrence equation: $$x_n=r^{n-1}a+\left(\frac{r^{n-1}-1}{r-1}\right)d, \qquad (n=1,2,3,...)$$ and the next stage in the text shows the equation ...
0
votes
1answer
613 views

recurrence relation on bank interest

Invest 1000 dollars at bank at 3 percent interest compound annually. Every year the bank deducts 15 dollars in charges. If $A_n$ is the value of the investment at the end of $n$ years write down a ...
2
votes
1answer
335 views

Proof of closed form Hofstadter G-Sequence

I'm working through a discrete maths text book and was stumped as to how to prove the closed form solution of the Hofstadter G-Sequence $a(0) = 0$ and $a(n) = n - a(a(n-1)), n \geq 1$ The closed ...