0
votes
0answers
44 views

Solving the recurrence $F(0) = X$ and $F(i)=A \cdot (F(i-1))^2 + B \cdot F(i-1) + C$

Moderator Note: This is a current contest question on codechef.com. I am given $F(0)=X$ and $F(i)=A \cdot (F(i-1))^2 + B \cdot F(i-1) + C$ for $1 \leq i \leq N$. Now given $N,A,B,C$ and $X$, how ...
5
votes
2answers
103 views

$a_1=1,a_{n+1}=\frac{n}{a_n}+\frac{a_n}{n}$. Prove that for $n\ge4$, $\lfloor{a_n^2}\rfloor=n$

Define a sequence $\left\lbrace a_{n}\right\rbrace$ by $\displaystyle{a_{1} = 1\,,\ a_{n + 1} = {n \over a_n} + {a_n \over n}.\quad}$ Prove that for $n \geq 4,\,\,\left\lfloor ...
3
votes
1answer
198 views

Minimum period of function such that $f\left(x+\frac{13}{42}\right)+f(x)=f\left(x+\frac{1}{6}\right)+f\left(x+\frac{1}{7}\right) $

Let $ f$ be a function from the set of real numbers $ \mathbb{R}$ into itself such for all $ x \in \mathbb{R},$ we have $ |f(x)| \leq 1,f(x)\neq constant $ and ...
9
votes
3answers
273 views

The integer $c_n$ in $(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$

For non-negative integer $n$, write $$(1+4\sqrt[3]2-4\sqrt[3]4)^n=a_n+b_n\sqrt[3]2+c_n\sqrt[3]4$$ where $a_n,b_n,c_n$ are integers. For any non-negative integer $m$, prove or disprove ...
-2
votes
1answer
564 views

Solve: $T(n) = T(n-1) +(1/n)$ by iteration

Use iteration method to solve: $1.$ $T(n) = T(n-1) + \frac{1}{n},\,(T(0)=1)$ $ 2.$ $T(n) = 3T\left(\dfrac{n}{3}\right) +1,\,(T(3)=1)$
1
vote
1answer
90 views

A recurrence relation with words, contest type problem

For a positive integer $n$, a $n$-word is a string of $n$ letters, where each letter is an $A$ or $B$. Let $p_n$ be the number of $n$-words not containing four consecutive $A$ and not containing three ...
-6
votes
1answer
749 views

How to find a Recurrence Relation from a word problem?

Suppose you have 5 kinds of wooden blocks: red blocks which are 2 inches high, blue blocks which are 2 inches high, green blocks which are 2 inches high, yellow blocks which are 3 inches high, and ...
-2
votes
1answer
493 views

Find a closed form for a generating function and recurrence

Find a closed form for the generating function $R(x) = \sum_{n=0}^\infty r_nx^n$, where $r_n$ is given by the recurrence $r_n = 3r_{n-1} + 5r_{n-2} + 6n$ for $n \geq 2$ and initial conditions $r_0 = ...
7
votes
2answers
941 views

Numerical method for finding the square-root.

I found a picture of Evan O'Dorney's winning project that gained him first place in the Intel Science talent search. He proposed a numerical method to find the square root, that gained him $100,000 ...
6
votes
1answer
313 views

Proving or disproving $f(n)-f(n-1)\le n, \forall n \gt 1$, for a recursive function with floors.

The Olympiad-style question I was given was as follows: A function $f:\mathbb{N}\to\mathbb{N}$ is defined by $f(1)=1$ and for $n>1$, by: ...
4
votes
2answers
141 views

A mouse leaping along the square tile

A $n \times n$ square is made of square tiles of dimensions $1\times1$. A mouse can leap along the diagonal or along the side of square tiles. In how many ways can the mouse reach the right lower ...
2
votes
1answer
142 views

Explicit formula for sequence with parity-based recursion

How do we find an explicit formula for the sequence $(a_i)_{i=1}^\infty$ in terms of $a_1=C$ if $$a_{i+1}=\begin{cases} a_i-13 & i \text{ even}, \\ 2a_i & i \text{ odd}.\end{cases}\quad i\ge2 ...