Proving an expression is perfect square

I have this expression I got in one larger exercise: (2+√3)2n+1+(2−√3)2n+1−46(2+√3)2(n+1)+1+(2−√3)2(n+1)+1−46+1 and i need to prove it is perfect square. I tried many different approaches but couldn’t find way to show it is square. Interesting fact is (2+√3)(2−√3)=1 so I tried replacing (2+√3)=x and (2−√3)=1/x to see if I would get an idea. Alternative form … Read more

How to solve the recurrence T(n) = T(⌈n/2⌉) + 1 is O(lg n)?

How do you solve the recurrence T(n)=T(⌈n/2⌉)+1 is O(lgn)? In this explanation, I don’t understand how the guess is made: We guess T(n)≤clg(n−2): T(n)≤clg(⌈n/2⌉−2)+1≤clg(n/2+1−2)+1 ≤clg((n−2)/2)+1≤clg(n−2)−clg2+1 ≤clg(n−2) Answer Here is the very clear answer in this image. I’m writing this because this is compulsory otherwise I don’t find text is important. So you want this answer … Read more

Recurrence relations help please? [closed]

Closed. This question is off-topic. It is not currently accepting answers. Want to improve this question? Update the question so it’s on-topic for Mathematics Stack Exchange. Closed 6 years ago. Improve this question How do I solve this recurrence relation? ak=ak−1+k when a0=2. Answer hint: ak=(ak−ak−1)+(ak−1−ak−2)+⋯+(a2−a1)+(a1−a0)+a0=k+(k−1)+(k−2)+⋯+2+1+2 AttributionSource : Link , Question Author : Ben , … Read more

Solve pn+1+16pn=12(56)n−1p_{n+1} + \frac 16 p_n = \frac 1 2 (\frac 5 6 ) ^{n-1}

I’m trying to solve: pn+1+16pn=12(56)n−1 with initial condition: p1=1. First, I search particular solution of the form p∗n=λ(56)n. I found λ=35. Next, I know that pn=α(−16)n+35(56)n, and using p1=1, I found: α=−3. Which leads to: pn=−3(−16)n+35(56)n. Well… But thanks to the recurrence formula, I have p2=14 and with this new formula, I have p2=13. Where … Read more

Help with recurrence T(n)=T(n/2)+nT(n) = T(n/2) + n

I just need help seeing where I went wrong in this solution. T(n)=T(n2)+n,   T(1)=0 By master theorem, this is θ(n). However, when I try to solve it, it doesn’t come out right. Where is my logic error? T(n)=T(n2)+n T(n)=T(n4)+n+n T(n)=T(n8)+n+n+n T(n)=T(n16)+n+n+n Thus, the pattern appears to be: T(n)=T(n2k)+kn,   k>0 If we assume n=2k, T(n)=T(nn)+kn T(n)=T(1)+kn T(n)=0+kn T(n)=kn … Read more

Prove that $(2n+1)k_{n+1}=(2n+1)k_{n}+\cos^{2n+1} (x)$

Given that $$k_n=\int \frac{\cos^{2n} (x)}{\sin (x)} dx$$ Prove that $$(2n+1)k_{n+1}=(2n+1)k_{n}+\cos^{2n+1} (x)$$ I have tried to prove this is true by differentiating both sides with product rule: $$2k_{n+1}+\frac{\cos^{2n+1} (x)}{\sin (x)}(2n+1)=2k_n+\frac{\cos^{2n} (x)}{\sin (x)}(2n+1)+(2n+1)\cos^{2n} (x) \sin (x)$$ I am stuck here as I met a dead end upon grouping and expanding. Please help. Thank you in advance!! Answer … Read more

Help me understand this sequence problem

Today, I encountered a problem in “Problem-Solving Strategies” by Arthur Engel (Chapter $9$. Sequences, page-$225$): Prove that there does not exist a monotonically increasing sequence of nonnegative integers $a_1,a_2,a_3,…$ so that $a_{nm}=a_n+a_m$ for all $n,m \in \mathbb{N}$. I could not prove it. So, I checked the solution provided in the book. It was: Solution: For … Read more

Finding a combinatorial recurrence relation with three variables

This question is from the generating functionology textbook, Let f(n, m,k) be the number of strings of n 0’s and 1’s that contain exactly m 1’s, no k of which are consecutive. Find a recurrence formula for f. It should have f(n, m,k) on the left side, and exactly three terms on the right. There … Read more

How to form a recurrence for a $n$-digit sequence using digits $0,1,2,3$ so that we have even no of $0$’s?

If we assume $T(n)$ to be the function representing the case where we have even number of $0$’s then $T(1)=3$ precisely strings $1, 2$ and $3$. $T(2)= 10$ ($00,11,22,33,12,21,13,31,23,32$). Likewise I got $T(3)=36$ and $T(4)=124$. Now how to proceed from here? Answer Consider a representation with even number of zeros at step $n-1$. At the … Read more

A square root solving algorithm invented by my friend

Recently, my friend told me a square root algorithm: {pn+1=pn+aqnqn+1=pn+qn Finally, pn/qn is near √a. But I’m not quite understand this method, we can rewrite the expression like this pn+1qn+1=pnpn+qn+aqnpn+qn and it just looks like the mean value formula λ+(1−λ)a I don’t know how it works and how to understand it intuitively. Answer Actually, it’s … Read more