We have this recursive formula defined $a_1=3$ &amp;   $a_n = a_{\lfloor{n/2}\rfloor} + a_{\lceil{n/2}\rceil} + 3n + 1$ for $n \geq 2$.  And we need to prove $n \leq 2^k \Longrightarrow a_n \leq 3 *  k2^k+4*2^k-1$ for all $n,k \in \mathbb{Z}^+$.  I think we wanna do the induction over k  For our basic case we choose $n = 2 , k = 1$   $a_2 = a_{\lfloor{2/2}\rfloor}+a_{\lceil{2/2}\rceil}+3*2+1 =$   $ 3 + 3 + (6+1) = 13$  $2\leq2^1 \Longrightarrow 13 \leq 3*1*2^1+4*2^1-1$  $2\leq2 \Longrightarrow 13 \leq 13$  Our basic case is proven, so we can move on to the induction step  So we will assume that the expression is true for $n \leq 2^k$ and we will now show it is true for $n \leq 2^{k+1}$  This is where I have kinda reached a dead end. My guess is that we want to move from $n \leq 2^k \Longrightarrow a_n \leq 3 *  k2^k+4*2^k-1$   to  $n \leq 2^{k+1} \Longrightarrow a_n \leq 3 *  (k+1)2^{k+1}+4*2^{k+1}-1$  And we could get closer to the P(k+1) expression by multiplying by 2 on both  sides of P(k) like this: $n*2 \leq 2^k*2 \Longrightarrow a_n*2 \leq (3 *  k2^k+4*2^k-1)*2$  But I don't know
105535
Via induction I need to prove an expression is true. the expression is:  $n \leq 2^k \longrightarrow a_n \leq 3 \cdot k2^k + 4 \cdot  2^k-1$  for all $n,k \in \mathbb{Z^+}$  $a_n$ is a recursive function where  $a_1 = 3$  $a_n = a_{\lfloor \frac{n}{2} \rfloor} + a_{\lceil \frac{n}{2} \rceil} + 3n+1$  I am stuck at the point where I need to prove that $P(n+1)$ is true  $a_{\lfloor \frac{n+1}{2} \rfloor} + a_{\lceil \frac{n+1}{2} \rceil} + 3(n+1) + 1 \leq 3 \cdot k  2^k + 4 \cdot 2^k -1  $   It is the fact that I don't know how to rewrite the floor and ceiling functions to something else.   Can someone give me some ideas how to proceed with this?
112375
The exercise asked me to proof $1^3=1$ $2^3=3+5$ $3^3=7+9+11$ $...$ I formulate the equation as (1)$$a^3 = \sum_{i=0}^{a-1} (a-1)a+1+2i$$ Proof base case: $$1^3=\sum_{i=0}^{1-1} (1-1)(1)+1+2i=1$$ Proof (a+1) case: (2) $$(a+1)^3=a^3+3a^2+3a+1$$ (3) $$(a+1)^3=\sum_{i=0}^{(a+1)-1}((a+1)-1)(a+1)+1+2i=\sum_{i=0}^{a}(a)(a+1)+1+2i$$ factor out last summation term, so number of iterations match (1): $$\sum_{i=0}^{a-1}[(a)(a+1)+1+2i]+(a)(a+1)+1+2a=\sum_{i=0}^{a-1}[(a)(a+1)+1+2i]+a^2+3a+1$$ rearrange the summation term, so part of equation match (1): $$\sum_{i=0}^{a-1}[(a)(a-1)+1+2i]+\sum_{i=0}^{a-1}(2a)+a^2+3a+1$$ substitute summation with (1): (4) $$a^3+\sum_{i=0}^{a-1}(2a)+a^2+3a+1=a^3+(2a)(a-1)+a^2+3a+1=a^3+3a^2+a+1$$ From (2) I got $a^3+3a^2+3a+1$ but from (3) &amp; (4) I got $a^3+3a^2+a+1$ My result with induction is off by 2a. Can someone please help me to understand where I did wrong?
19423
I realize that there is probably not a closed form, but is there an efficient way to calculate the following expression?  $$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor$$  I've noticed $$\sum_{k=1}^n \left\lfloor \frac{n}{k}\right\rfloor = \left\lfloor\frac{1}{2}\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor} \left\lfloor\frac{n}{k}\right\rfloor\right\rfloor + \sum_{k=1,\ odd(k)}^n \left\lfloor \frac{n}{k}\right\rfloor$$  But I can't see an easy way to let the second term enter in a recursion.
118599
I am working on an assignment and have to write a proof for the following:  $$\lfloor 4x \rfloor =  \lfloor x \rfloor + \lfloor x+\frac{1}4 \rfloor + \lfloor x+\frac{1}2 \rfloor + \lfloor x+\frac{3}4 \rfloor$$  I have to do by proof by case I know the cases to be as follows  $$0 \le x-\lfloor x \rfloor \lt \frac 1 4$$ $$\frac 1 4 \le x-\lfloor x \rfloor \lt \frac 1 2$$ $$\frac 1 2 \le x-\lfloor x \rfloor \lt \frac 3 4$$ $$\frac 3 4 \le x-\lfloor x \rfloor \lt 1$$  The problem is I don't understand how I can express this.  Case 0 In this case I know that it would be $4n$ here  Case 1 In this case I know that it would be $4n+1$  Case 2 Here it would be $4n+2$  Case 3 Now the last case would end up being  $4n+3$  Can someone help me express this?
20493
Show that $ \left\lceil( \sqrt3 +1)^{2n}\right\rceil$ where $n \in  \mathbb{N}$ is divisible by $2^{n+1}$.     I wrote the binomial expansion of $ ( \sqrt3 +1)^{2n}$ and  $( \sqrt3 -1)^{2n}$ and then added them to confirm that the next integer is even. Afterwards I applied $AM \ge GM$ on the two terms to get $ ( \sqrt3 +1)^{2n} + ( \sqrt3 -1)^{2n} \ge (2^{n+1})$.  Now I'm unable to figure out the next step. Any help would be appreciated. :)
29076
I have a Recurrence: $$a_{0}=1$$ $$  a_{n}=\sum_{k=0}^{n-1}(n-k)a_{k}$$ I have evaluated some a's:$a_{0}=1, a_{1}=1,a_{2}=3,a_{3}=8,a_{4}=21,a_{5}=55,...$. In the previous exercise on had to derive a generating Function for the even indexted Fibonacci Numbers. So these are definitely $F_{0}=1,F_{1}=1,F_{2}=3,F_{3}=8,F_{4}=21,...$   Then I had a detailed look on the summation: $$a_{0}=1$$ $$a_{1}=(1-0)*1=1$$ $$a_{2}=(2-0)*a_{0}+(2-1)*a_{1}=2*1+1*1=3$$ $$a_{3}=(3-0)*a_{0}+(3-1)*a_{1}+(3-2)*a_{2}=3*1+2*1+1*3=8$$ $$a_{4}=(4-0)*a_{0}+(4-1)*a_{1}+(4-2)*a_{2}+(4-3)*a_{3}=4*1+3*1+2*3+1*8=21$$  Its obviously linked to:    But i dont see how to proceed.
53397
I'm having trouble solving this problem. I have relation for two sequences of natural numbers.   $$a(n)+\sqrt3\cdot b(n)=\left(1+\sqrt3\right)^n$$  and I have to prove that recursions:  $$\begin{align*} &amp;a(n+1)=a(n)+3b(n)\\ &amp;b(n+1)=a(n)+b(n) \end{align*}$$  will satisfy relation mentioned above. I tried solve it using induction but I failed. Can anybody help with some other ideas?
49380
How can I show that $n^2&lt;n!$ for all $n\geq 4$ Step 1 For $n=1$, the LHS=$4^2=16$ and RHS=$4!=24$. So LHS$&lt;$ RHS. Step 2 Suppose the result be true for $n=k$  i.e., $k^2&lt;k!$ Step 3 For $n=k+1$ $(k+1)^2=k^2+2k+1$ What will be the next step?
13678
Use induction to prove that $2^n \gt n^3$ for every integer $n \ge 10$.  My method:  If $n = 10$, $2^n \gt n^3$ where $2^{10} \gt 10^3$ which is equivalent to $1024 \gt 1000$, which holds for $n = 10$. $2^k \gt k^3$.   $2^{k + 1} \gt (k + 1)^3$  $2^{k + 1} \gt (k + 1)(k + 1)(k + 1)$  $2^{k + 1} \gt (k^2 + 2k + 1)(k + 1)$  $2^{k + 1} \gt (k^3 + 3k^2 + 3k + 1)$  $(k + 1) \cdot 2^k \gt k^3 + 3k^2 + 3k + 1$  Since $2^{10} \gt 10^3$, the inequality holds for $n = 10$. Assume $2^k \gt k^3$ for $k \ge 10$. We show that $2^{k + 1} \gt (k + 1)^3$. Hence, $2^{k + 1} = 2 \cdot 2^k \gt 2k^3$  $= k^3 + k^3 \ge k^3 + 10k^2$  $= k^3 + 10k^2 = k^3 + 4k^2 + 6k^2 \ge k^3 + 4k^2 + 6 \cdot 10 = k^3 + 4k^2 +60$  $k^3 + 4k^2 + 60 \gt k^3 + 3k^2 + 3k + 1$  Therefore, $2^{k + 1} \gt (k + 1)^3$. Hence, $2^n \gt n^3$ for every integer $n \ge 10$.  I was trying to fix this but I am not sure how to go about doing so.
69106
let $n \gt 1$ be an integer, and consider n people; $P_1,P_2,...,P_n$ let $A_n$ be the number of ways these $n$ people can be divided into groups, such that each group have either one or two people  determine $A_1,A_2,A_3$ So I have  $A_1=1$ way   $A_2=2$ way   $A_3=4$ way  and from this I derive the formula $A_n = 2^{n-1}$ but this is not true for $n\ge 4$  so I have to prove that for each integer $n\ge 3$  $$A_n = A_{n-1} + (n-1) * A_{n-2}$$  So I proved this by Induction:  Where I assumed that $n \ge 2$ so $A_{n+1} = 2^n$  So I did the induction step.. and I was wrong  I was hoping anyone on here could help me by proving this with induction?  Thanks
44967
I think I have sort of a proof of the following nested radical expression due to Ramanujan for $x\ge 0$.     $$\large x+1=\sqrt{1+x\sqrt{1+(x+1)\sqrt{1+(x+2)\sqrt{1+\cdots}}}}$$ for $ x\ge -1$   I just want to know if my proof is okay or there is a flaw, and if there is one I request to give some suggestions to eliminate them. Thank you. The proof is the following:  Proof: Let us define $$ a_n(x)=\underbrace{\sqrt{1+x\sqrt{1+(x+1)\sqrt{1+(x+2)\sqrt{1+\cdots}}}}}_{n \ \mbox{terms}}$$ for $x\ge 0$ so that $$ a_1(x)=\sqrt{1+x},\ a_2(x)=\sqrt{1+x\sqrt{1+(x+1)}},\ a_3(x)=\cdots$$    and so on. Since $x\ge 0$ each one of the $a_n$ is defined (I am taking only the positive square root). Also, we note that $$a_{n+1}^2(x)=1+xa_{n}(x+1)$$  Now, we note that $\{a_n(x)\}$ is an increasing sequence and that $$a_n(x)&lt;x+1$$ $\forall n\ge 1$, this is easy to prove by induction as below:  For $n=1$, $a_1(x)=\sqrt{1+x}&lt;1+x$ since $x\ge 0\Rightarrow 1+x\ge 1$. SO it is true for $n=1$. Similarly, the truth can be proved for $n&gt;1$.  Then $a_n(x)$ converges to $$l(x)=\sup_{n}a_n(x)\le x+1$$ Now I make the following claim:  Claim: $l(x)=x+1\quad \forall i\ge 0$  Proof: Fix $x$. Let $l(x)&lt;x+1$. Then, $l(x)=x+1-\epsilon$ for some $\epsilon&gt;0$. Now, I claim that there must be a $n$ such that $$x+1-a_n(x)&lt;\epsilon$$, and if that is true then $$a_n(x)&gt;x+1-\epsilon=l(x)$$ which is a contradiction since $$l(x)=\sup_{n}a_n(x)$$ and then it implies that $$l(x)=x+1$$ To prove my claim it requires $$x+1-a_n(x) &lt;  \epsilon$$ Now, \begin{align} x+1-a_n(x) = &amp; x+1-\sqrt{1+xa_{n-1}(x+1)} \\ \ =&amp; \frac{(x+1)^2-({1+xa_{n-1}(x+1)})}{x+1+\sqrt{1+xa_{n-1}(x+1)} } \\ \ =&amp; x\frac{(x+1)+1-a_{n-1}(x+1)}{x+1+\sqrt{1+xa_{n-1}(x+1)} } \\ \ &lt;&amp; \frac{x}{x+2}((x+1)+1-a_{n-1}(x+1))\\ \ &lt;&amp; \frac{x}{x+2}\cdot\frac{x+1}{x+3}((x+2)+1-a_{n-2}(x+2))\\ \ &lt;&amp; \frac{x}{x+n-1}\cdot \frac{x+1}{x+n} ((x+n-1)+1-a_{1}(x+n-1))\\ \ &lt;&amp; \frac{x}{x+n-1}\cdot \frac{x+1}{x+n}(x+n-\sqrt{x+n})\\ \ &lt;&amp; \frac{x(x+1)}{x+n-1} \end{align}  Now, if one is able to find $n$ such that $$\frac{x(x+1)}{x+n-1}&lt;\epsilon \Rightarrow x&lt; \frac{-(1-\epsilon)+\sqrt{(1-\epsilon)^2+4\epsilon(n-1)}}{2}$$ then we're done.   Now from the upper bound it seems that there always exists some $n$ that satisfies this requirement. Hence the claim is proved.
23125
I aim to show that $$(n+1)^n&lt;n^{(n+1)}$$ for all $n \geq 3$. I tried induction, but it didn't work. What should I do?
70085
Problem: $2^n &gt; n^2, \forall n \in \mathbb{N} , n \geq 5$ Base: $2^5 &gt; 5^2$ Induction Hypothesis: Assume for $n = k \geq 5$ that $2^k&gt;k^2$ Inductive Step: $$2^k &gt; k^2$$ $$2^k \times  2 &gt; k^2 \times 2$$ $$2^{k+1} &gt; 2k^2$$ From there I can finish the proof by asserting that $k^2 &gt; 2k+1, \forall k \in \mathbb{N} , k \geq 3$. Do I need to prove that $k^2 &gt; 2k+1, \forall k \in \mathbb{N} , k \geq 3$. Or can I substitute it into my inequality?
63335
Prove that $1&lt;\dfrac{1}{n+1}+\dfrac{1}{n+2}+...+\dfrac{1}{3n+1}$.  By using the Mathematical induction. Suppose the statement holds for $n=k$.  Then for $n=k+1$. We have $\dfrac{1}{k+2}+\dfrac{1}{k+3}+...+\dfrac{1}{3k+1}+\dfrac{1}{3k+2}+\dfrac{1}{3k+3}+\dfrac{1}{3k+4}=(\dfrac{1}{k+1}+\dfrac{1}{k+2}+\dfrac{1}{k+3}+...+\dfrac{1}{3k+1})+(\dfrac{1}{3k+2}+\dfrac{1}{3k+3}+\dfrac{1}{3k+4}-\dfrac{1}{k+1})$  we know $\dfrac{1}{k+1}+\dfrac{1}{k+2}+\dfrac{1}{k+3}+...+\dfrac{1}{3k+1}&gt;1$  What can we do for $(\dfrac{1}{3k+2}+\dfrac{1}{3k+3}+\dfrac{1}{3k+4}-\dfrac{1}{k+1})$?
88129
I have done a few normal inductions (like divisibility and sums) and know a little bit about strong induction. I can't find any problem similar to this one and am struggling to understand any intuition that would make proving this statement any easier. Here is how far I have gotten (not very much): Base Case: $4^1 &lt; 5^1$ $4^2 &lt; 5^2$ $16 &lt; 25$ Induction: $4^k &lt; 5^k$ $4^{k+1} &lt; 5^{k+1} = 4\times4^k &lt; 5\times5^k$ I have no clue where to go or how to force the k+1 equation to somehow equate to the k equation. Sorry if this has been asked before. Thank you.
118669
I found this in my math book. I have solved a). Exercise b) is to prove the derangement sum by induction.  A derangement of $n$ elements is a permutation where none of the elements keep its original placement. Let $a_n$ be the number of possible derangements of n elements. a) Show that $a_1=0$, $a_2=1$. Write all the derangements of the elements in $(A,B,C)$ and the elements in $(A,B,C,D)$. Show that the recursion formula is: $a_n = (n-1)(a_{n-1} + a_{n-2})$  My answer: For placing element $1$ there are $(n-1)$ possibilities. If field $i$ does not take element 1, there is one forbidden element for each field, and there are $a_{n-1}$ possibilities left. If field $i$ does take element $1$, the problem is reduced to $a_{n-2}$. Because of that the formula is $a_n = (n-1)\left(a_{n-1} + a_{n-2}\right)$.  b) Show by induction that: $a_n=n!\left[1 - \frac{1}{1!} + \frac{1}{2!} -... + (-1)^n\frac{1}{n!}\right]$.  My thoughts: I know how to prove it by the principle of inclusion and exclusion, but not induction. I guess the recursion formula from a) can be used.
110441
I know how to prove this by induction but the text I'm following shows another way to prove it and I guess this way is used again in the future. I'm confused by it.  So the expression for first n numbers is: $$\frac{n(n+1)}{2}$$  And this second proof starts out like this. It says since:  $$(n+1)^2-n^2=2n+1$$  Absolutely no idea where this expression came from, doesn't explain where it came from either.  Then it proceeds to say: \begin{align} 2^2-1^2&amp;=2*1+1 \\ 3^2-2^2&amp;=2*2+1\\ &amp;\dots\\ n^2-(n-1)^2&amp;=2(n-1)+1\\ (n+1)^2-n^2&amp;=2n+1 \end{align} At this point I'm completely lost. But it continues to say "adding and noting the cancellations on the left, we get" \begin{align} (n+1)^2-1&amp;=2(1+2+...+n)+n \\ n^2+n&amp;=2(1+2+...+n) \\ (n(n+1))/2&amp;=1+2+...+n \end{align}  Which proves it but I have no clue what has happened. I am entirely new to these math proofs. Im completely lost. I was great at high school math and calculus but now I haven't got the slightest clue of what's going on. Thanks