I have a question. I must prove with induction that $$\displaystyle 2^{2n+1} - 9n^{2} + 3n - 2$$ is divisible by $54$. My attempt was that if I plug in $n = 0$, I get result of $0$. Then I want to show this sentence for $n + 1$: $2^{2(n+1) + 1} - 9(n + 1)^2 + 3(n + 1) - 2 = 2^{2n + 3} - 9n^2 - 18n - 9 + 3n + 3 - 2 = (2^{2n + 1} \cdot 4 - 9n^2 + 3n - 2 ) - 18n - 6 = (3 \cdot 2^{2n + 1} - 18n - 6) + \left(2^{2n + 1} - 9n^{2} + 3n - 2\right)$. Here I stopped, because I don't know how to manipulate the prove. Can anyone help me?
122043
What I get is $4 \cdot 54k + 27(n(n-1)) - 2$.  I understand first two terms but $-2$ is giving me a headache. I suppose to be true every term should be divisible by $54$. Or did I make wrong conclusion?  P. S: Is there mathjax tutorial?
115709
Proving by induction. We'd like to show that $2 + 4 + 6 + \cdots+ 2n = n(n + 1)$.  A nice way to do this is by induction. Let $S(n)$ be the statement above. An inductive proof would have the following steps:  Show that $S(1)$ is true.  Show that if $S(1),\ldots,S(k)$ are true, then so is $S(k + 1)$.    This question is really starting to bug me, am I doing something wrong or is the equation wrong for that series? It only seems to work for $S(1)$ but after that it does not give the correct series. The $n(n+1)$ series is $2, 6, 12,\ldots.$ I'm really confused can someone please nudge me in the right direction (I know how proofs by induction works) I'm just having problems with this one in particular.
95113
I want to show that $n+1$ is a divisor of $\displaystyle\binom{2n} {n}$, for all $n\in\mathbb{N}.$  I have tried to show it by induction and Pascal's rule but it did not worked out.  I would appreciate some help.
44709
I'm trying to prove using induction that $9$ divides $n^3 + (n+1)^3 + (n+2)^3$ whenever $n$ is a non-negative integer. So far, I have:   Base case: $P(1) = (1) + (8) + (27) = 36, 36$ can be divided by $9$ so the base case is valid Inductive step: let $P(n)$ be the statement $9$ divides $n^3 + (n+1)^3 + (n+2)^3$. Assume $P(k)$ is true, so $9$ divides $k^3 + (k+1)^3 + (k+2)^3$.   And this is where I'm stuck. I'm not sure how to demonstrate that $9$ divides $P(n)$ when $n = k+1$. If someone could step me in the right direction that would be awesome. Thanks!
111685
I need to prove  $2n \leq 2^n$, for all integer $n≥1$ by mathematical induction?  This is how I prove this:  Prove:$2n ≤ 2^n$, for all integer $n≥1$  Proof: $2+4+6+...+2n=2^n$  $i.)$ Let $P(n)=1         P(1): 2(1)=2^1\implies 2=2$.        Hence, $P(1)$ is true.  $ii.)$  Assume that $P(n)$ is true for $n=k$, i.e, $2+4+6+...+2k=2^k$, and prove that $P(n)$ is also true for $n=k+1$, i.e, $2+4+6...+2(k+1)=2^{(k+1)}$  from the assumption add $2(k+1)$ on both sides so we have   $2+4+6...2k+2(k+1)=2^k+2(k+1)$  I'm confused with $2^k+2(k+1)$, I don't know how to make $2^k$ be equivalent to $2^{k+1}$.  I feel i'm doing something wrong.   Any help would be appreciated!
115268
Prove by induction: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$ for all $n\in \mathbb{N}$.   Today I wrote calculus exam, I had this problem given.  I have the feeling that I will get $0$ points for my solution, because I did this:   Base Case: $n=1$ $$\sum_{k=1}^{1} \binom 1 1 = 1 =  2^1 -1 .$$  Induction Hypothesis: for all $n \in \mathbb{N}$: $$\sum_{k=1}^{n} \binom n k = 2^n -1 $$  Induction Step: $n \rightarrow n+1$ $$\sum_{k=1}^{n+1} \binom {n+1} {k} = \sum_{k=1}^{n} \binom {n+1} {k} + \binom{n+1}{n+1} = 2^{n+1} -1$$  Please show me my mistake because next time is my last chance in this class.
60337
Here's the full question:  Prove that, for any $n + 1$ integers, $\{x_0, x_1, x_2, . . . , x_n\}$, there exist two integers $x_i$ and $x_j$ with $i \neq j$ such that $x_i − x_j$ is divisible by $n$.  Now, the integers aren't necessarily consecutive, positive, or without repeats. I've tried breaking this into cases, such as "$x_i = x_j, \dfrac{0}{n} = 0$" etc. But I don't think it's possible to exhaust the cases.  I feel like there should be an easy way to contradict this one, by saying that $x_i - x_j$ isn't divisible by $n$. But I just wasn't getting anywhere with that one.  I thought about using induction, but I would have just as hard a time proving this for $n$ integers before $n+1$ integers, so I don't think it would be possible for me to do it that way.  If anyone could help out, that would be wonderful. I'm pretty stuck here.
68440
$\displaystyle\sum_{i=0}^n2^i=2^{n+1}-1$.  I don't understand induction so I could use some help.
10019
I did some mathematical induction problems on divisibility   $9^n$ $-$ $2^n$ is divisible by 7. $4^n$ $-$ $1$ is divisible by 3. $9^n$ $-$ $4^n$ is divisible by 5.   Can these be generalized as $a^n$ $-$ $b^n$$ = (a-b)N$, where N is an integer? But why is $a^n$ $-$ $b^n$$ = (a-b)N$ ?  I also see that $6^n$ $- 5n + 4$ is divisible by $5$ which is $6-5+4$ and $7^n$$+3n + 8$ is divisible by $9$ which is $7+3+8=18=9\cdot2$.  Are they just a coincidence or is there a theory behind?  Is it about modular arithmetic?
67724
Provided the following sequence of integers $t_1, t_2, t_3$,... is defined as:    $t_1 =4, t_2 =8$ and $t_n= $ $ 6t_n$$_-$$_1$ - $4t_n$$_-$$_2$ for all integers $n \geq 3$   How do we prove that $2^n$ divides $t_n$ for all integers $n \geq 1$ by strong induction?  So far, I am having problems with the induction step as I am still trying to grasp the concept of strong induction, but this is what I came up with so far:  Base step:  $t_3 = 32$, which is divisible by 8; and $t_4 = 160$, which is divisible by 16.  $\therefore$ Statement is true when $n=3$ and $n=4$.  Induction step:  Assuming $k=n$ and the statement is true for $3,4,...k$. Prove that $2^k$ divides $t_k$ for $k+1$:  $t_3 = ((2^3 - 2)(2^3) - (2^2)(2^2)) = 2^6 - 2^4 - 2^4 $; dividing this by $2^3$ gives $2^3 - 2^2$ which would be an integer result.  $t_4 = ((2^3 - 2)(2^5) - (2^2)(2^3)) = 2^8 - 2^6 - 2^5 $; dividing this by $2^4$ gives $2^4 - 2^2 - 2$ which would also be an integer result.  $\therefore$ By the logic above, the statement also holds for $k-1$, $k$ as well as $k+1$, thus as required to prove by strong induction.  I believe this is a fundamentally flawed way of trying to prove by strong induction, but this is the only way I can possibly think of. Can someone show a correct method of solving this?
10664
My textbook provided the following proof:        Base case: When $n=0, 9^n-8n-1=0=64\cdot0$, so $64\mid\left(9^n-8n-1\right)$.      Induction step: Suppose that $n\in\mathbb N$ and $64\mid\left(9^n-8n-1\right)$. Then there is some integer $k$ such that $9^n-8n-1=0=64k$. Therefore:      $$\begin{align} 9^{n+1}-8(n+1)-1&amp;=9^{n+1}-8n-9\\ &amp;=9^{n+1}-72n-9+64n\\ &amp;=9\left(9^n-8n-1\right)+64n\\ &amp;=9(64k)+64n\\ &amp;=64(9k+n) \end{align}$$      so $64\mid\left(9^{n+1}-8(n+1)-1\right)$.      What I don't understand is how the equation goes from   $$= 9^{n+1} - 8n - 9$$  to   $$= 9^{n+1} - 72n - 9 + 64n$$
50190
I'm trying to prove the above result for all $n\geq1$ but after substituting in the inductive hypothesis, I end up with a result that is not quite obviously divisible by 9.   Usually with these divisibility induction problems, it falls apart nicely and we can easily factorise say a 9 if the question required us to prove that the expression is divisible by 9. However in this case, I do not end up with such a thing.  My work so far below:  Inductive Hypothesis: $7^k(3k+1)-1=9N$ where $N\in\mathbb{N}$  Inductive Step:  $7^{k+1}(3k+4)-1 \\ =7\times 7^k(3k+1+3)-1 \\ =7\times \left [ 7^k(3k+1)+3\times 7^k \right ] -1 \\ = 7 \times \left [ 9N+1 + 3 \times 7^k \right ] -1 \\ = 63N+21\times 7^k+6 \\ = 3 \left [ 21N+7^{k+1}+2 \right ]$   So now I need to somehow prove that $21N+7^{k+1}+2$ is divisible by 3, but I'm not quite sure how to proceed from here...
25419
Prove by induction that $5^n - 1$ is divisible by $4$.   How should I use induction in this problem. Do you have any hints for solving this problem?  Thank you so much.
118808
Question:  Prove by mathematical induction that $$(1)+(1+2)+(1+2+3)+\cdots+(1+2+3+\cdots+n)=\frac{1}{6}n(n+1)(n+2)$$ is true for all positive integers n.  Attempt:  I did the the induction steps and I got up to here: $$RTP:\frac{1}{6}n(n+1)(n+2)+(1+2+3+\cdots+n+(n+1))=\frac{1}{6}(n+1)(n+2)(n+3)$$ Where do I go from here?  Thank you very much.
43298
For any odd positive integer $k\geq1$, the sum $1^k+2^k + \dots + n^k$ is divisible by $n(n+1)\over 2$.   I used induction principle for the solution but cannot prove it.  I took $P(k) = 1^k+2^k+\dots+n^k$.  For $P(1)$ it is true.  For $P(n)$ let it be true.  But for $P(n+1)$ I cannot solve it.
85986
I am confused as to how to solve this question.  For the Base case $n=1$, $(2^{2(1)} - 1)\,/\, 3 = 1$, base case holds  My induction hypothesis is: Assume $2^{2k} -1$ is divisible by $3$ when $k$ is a positive integer  So, $2^{2k} -1 = 3m$   $2^{2k} = 3m+1$  after this, I'm not quite sure where to go.  Can anyone provide any hints?
9946
As homework, I have to prove that     $\forall n \in \mathbb{N}: n^3-n$ is divisible by 6   I used induction  1) basis: $A(0): 0^3-0 = 6x$ , $x \in \mathbb{N}_0$ // the 6x states that the result is a multiple of 6, right?  2) requirement: $A(n):n^3-n=6x$  3) statement: $A(n+1): (n+1)^3-(n+1)=6x$  4) step: $n^3-n+(n+1)^3-n=6x+(n+1)^3-n$  So when I resolve that I do get the equation: $n^3-n=6x$ so the statement is true for $\forall n \in \mathbb{N}$  Did I do something wrong or is it that simple?