# Tag Info

3

To show that $r_n = 3\cdot 2^n - 4\cdot 5^n$ satisfy the equation then start by writing the equation as $$r_n - 7r_{n-1} + 10r_{n-2} = 0$$ Now calculate $r_n, r_{n-1}$ and $r_{n-2}$ from the formula. This gives us $$r_n = \color{red}{3\cdot 2^n - 4\cdot 5^n}$$ $$r_{n-1} = 3\cdot 2^{n-1} - 4\cdot 5^{n-1} = \color{blue}{\frac{3}{2}\cdot 2^{n} - ... 2$$7r_{n-1}-10r_{n-2}=7(3.2^{n-1}-4.5^{n-1})-10(3.2^{n-2}-4.5^{n-2})7r_{n-1}-10r_{n-2}=(42-30).2^{n-2}+(-140+2=40)5^{n-2}7r_{n-1}-10r_{n-2}=3.2^n-4.5^n7r_{n-1}-10r_{n-2}=r_n$$2 Wolfram Alpha gives the roots as -1 and 1/6 (3\pm i \sqrt(3)). This last is \frac{1\pm i\sqrt{1/3}}{2} which is your answer. My guess is either you misread WA's answer or you entered the equation incorrectly. 2 i am going to try. the defining relation for f gives us the inequality$$nf(n) = n\{f(f(n-1)) + 1\} =n + nf(f(n-1)) \ge n $$because the range of f consists of positive integers. we can use jf(j) \ge j again and again to get$$ nf(n) \ge n + nf(f(n-1)) \ge n + nf(n-1) \ge n + n(n-1) = n^2$$therefore$$1f(1) + 2f(2) + \cdots + nf(n) \ge 1^2 + 2^2 + ...

2

If $f(x)=f(y)$ then $f(x+1)=f(f(x))+1=f(f(y))+1=f(y+1)$, so $f(n)$ is periodic. But every number $f(m)$ in the cycle is one more than another number in the cycle. This is a contradiction, so $f(x)\neq f(y)$ when $x\neq y$. $f(n+1)=f(f(n))+1>f(f(n))$, so $f(n+1)$ is never the lowest value that $f(x)$ takes. So $f(1)$ must be the lowest value that $f(x)$ ...

2

When we have given an linear recurrence equation of a sequence such as your case : $$y(n+2)+2y(n+1)-3y(n) = -2n$$ The first point is to find the general solution of the associated homogeneous equation $$\tilde{y}(n+2)+2\tilde{y}(n+1)-3\tilde{y}(n) = 0$$ which you did $\tilde{y}(n) = c_1(-3)^n+c_2$. (the general method consist to solve the associated ...

1

I can compute $DP[i][j][k]$ in $O(N^2)$. To see this, note that the first term of the summation ($DP[i][m][0]$) can always be computed in $O(1)$, and the second term of the second term of the summation ($j$ from $DP[m+1][j][k-1]$)... is always $j$. ...assuming everything is memoized, of course.

1

Pick d) as an example. You are given $a_0 = -1, a_1 = 0$. The recurrence formula is $a_n = n a_{n-1} + a_{n-2}^2$, so setting $n=2$ gives $a_2 = 2 a_1 + a_0^2$, and evaluating gives $a_2 = 1$. Repeating for $n=3$ gives $a_3 = 3 a_2 + a_1^2$ and evaluating gives $a_3 = 3$. Etc, etc.

1

A general first order recurrence relation $$a_{n+1} - f_n a_n = g_n \longrightarrow (1).$$ admits the following solution $$a_n = \left(\prod_{k=0}^{n-1} f_k \right) \left(a_0 + \sum_{m=0}^{n-1}\frac{g_m}{\prod_{k=0}^m f_k}\right).$$

1

let $$\dfrac{h_{n-1}}{h_{n}}=(1+cq^{n-1})p$$ so we have $$\dfrac{h_{n-2}}{h_{n-1}}=(1+cq^{n-2})p$$ $$\cdots\cdots$$ $$\dfrac{h_{1}}{h_{2}}=(1+cq)p$$ $$\dfrac{h_{1}}{h_{n}}=\prod_{k=1}^{n-1}(1+cq^k)p\Longrightarrow h_{n}=\dfrac{h_{1}}{\prod_{k=1}^{n-1}(1+cq^k)p}$$ then we have $$t_{n}=\dfrac{h_{n-1}}{h_{n}}t_{n-1}+an+b$$ $$\Longrightarrow ... 1 Since 1\cdot 1+ 2\cdot 2+ \cdots + n\cdot n = n(n+1)(2n+1)/6, it is enough to prove that f(n)\le n, for all n. We shall prove that f(n)\le n for all n, by full induction. Assume f(m)\le m for all m\le n. Let's prove that f(n+1) \le n+1. Let m=f(n) \le n. Then f(f(n))=f(m) \le m=f(n). So, f(n+1) = f(f(n))+1 \le f(n)+1 \le n+1. All ... 1 For the first, no, because F_n \approx \phi^n/\sqrt{5} where \phi =\dfrac{1+\sqrt{5}}{2} \approx 1.618 . For the second, yes, eventually for any k > 0 for the reason given above. 1 After correcting the typos, we have$$\begin{align*} A(z)&=2+z\sum_{n\ge 1}a_{n-1}z^{n-1}+z\sum_{n\ge 1}2^{n-1}z^{n-1}\\ &=2+z\sum_{n\ge 0}a_nz^n+z\sum_{n\ge 0}2^nz^n\\ &=2+zA(z)+z\sum_{n\ge 0}2^nz^n\;, \end{align*}$$since A(z)=\sum_{n\ge 0}a_nz^n. Now just subtract zA(z) from both sides to get$$(1-z)A(z)=A(z)-zA(z)=2+z\sum_{n\ge ...

1

With Abhishek Bakshi hint ,Now I have complete this answer, since $$\dfrac{a_{n}}{n!}=\dfrac{1}{2}\dfrac{a_{n-1}}{(n-1)!}+\dfrac{1}{2}\dfrac{a_{n-2}}{(n-2)!}+\dfrac{(-)^n(1-\dfrac{n}{2})}{n!}$$ let $b_{n}=\dfrac{a_{n}}{n!},b_{1}=0,,b_{2}=\dfrac{1}{2}$then we have $$b_{n}=\dfrac{1}{2}b_{n-1}+\dfrac{1}{2}b_{n-2}+\dfrac{(-)^n(1-\dfrac{n}{2})}{n!}$$ ...

1

How did you input the equation into Wolfram Alpha? You have as solutions  \begin{align} a_n&=(-1)^n\tag{1}\\[9pt] b_n &=\frac12\left[\,\left(\frac{1+\frac i{\sqrt{3}}}{2}\right)^n+\left(\frac{1-\frac i{\sqrt{3}}}{2}\right)^n\,\right]\\ &=\mathrm{Re}\left[\,\left(\frac{1+\frac i{\sqrt{3}}}{2}\right)^n\,\right]\tag{2}\\[9pt] c_n ...

Only top voted, non community-wiki answers of a minimum length are eligible