For questions about mathematical induction, a method of mathematical proof. Mathematical induction generally proceeds by proving a statement for some integer, called the *base case*, and then proving that if it holds for one integer then it holds for the next integer. This tag is primarily meant ...

learn more… | top users | synonyms

1
vote
3answers
80 views

prove combinatorical identity using induction

Question: prove by induction on $n+m$ the combinatoric identity: $$\sum_{k = 0}^n {m + k \choose k} = {m + n + 1 \choose n}$$ I've tried to do on both $n$ and $m$ but I think it isn't the right way. ...
0
votes
2answers
120 views

Prove $(1 - a)^n \geq 1 - na$ for $0 < a < 1$

This is exercise problem from "The Art of Computer Programming - Fundamental Algorithm". Prove by induction that if $0 < a < 1$, then $(1 - a)^n \geq 1 - na$ Here is my attempt: If n = ...
6
votes
1answer
343 views

Prove that $\,\sqrt [n] n < 1 + \sqrt{\frac{2}{n}}\,$

I am having difficulty proving the following inequality: $$ \sqrt[n]{n} < 1 + \sqrt{\frac{2}{n}} \quad \text{for all positive integers}\,\,\, n. $$ I am trying to use mathematical induction but I ...
3
votes
3answers
179 views

Binomial theorem $(a+b)^n=\sum \limits_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k}$ [duplicate]

I'm trying to understand the proof by induction of: $$ (a+b)^n = \sum \limits_{k=0}^{n}\binom{n}{k}a^{n-k}b^{k} $$ I'm at the point of deriving the inductive step and am getting next: $$ (a+b)^{n+1} = ...
0
votes
2answers
80 views

Using induction to prove $2^{n-1}(1 + a_1a_2\ldots a_n) \geq (1+a_1)(1+a_2)\ldots(1+a_n)$ for $a_i \geq 1$

Hello I have been blasting at this inequality proof and it is just not doing what I want it to do: Prove that $2^{n-1}(a_1a_2\ldots a_n + 1) \geq (1+a_1)(1+a_2)\ldots(1+a_n)$ assuming that ...
2
votes
1answer
72 views

Inductive proof of an inequality

I am trying to prove this inequality by induction: For all $x$ in the interval $x\in [0, \pi]$, prove that: $$ |\sin (nx)| \leq n\sin(x) \textit{, n a nonnegative integer}$$ The base case is ...
2
votes
2answers
60 views

How to prove $n^3 < 4^n$ using induction? [duplicate]

It's true for all Natural numbers. What I've got so far: Prove $P(0) \to $ base case: Let $n = 0$ $(0)^3 < 4^0 = 0 < 1$ Then $P(0)$ is true. Part Two: Prove $P(n) \Rightarrow P(n + 1) ...
2
votes
3answers
147 views

is it wrong to do this to solve an induction question

When doing an induction problem is it wrong to simply add the next variable to both sides? for example for all natural numbers $$4+9+14+19....+(5n-1)=\frac{n}{2}(3+5n)$$ assume true for k ...
1
vote
1answer
385 views

Show that any subgroup of a finitely generated abelian group is finitely generated?

I am working through Rotman 2.89 and I can't seem to solve this one. Note: Please do not link me to the related questions such as Proving that a subgroup of a finitely generated abelian group is ...
1
vote
1answer
66 views

Proof by induction for an unknown function, e.g. $\frac{\sum_{k=0}^n (k-1)\cdot (n-k-1)}{n^2} = \frac{n}{6} - \frac{1}{6n}$

I get how to do a proof by induction for say, a sum of all numbers or a sum of all numbers^2 function. But where do I start with a problem like: $$\frac{\sum_{k=0}^n (k-1)\cdot (n-k-1)}{n^2} = ...
0
votes
2answers
92 views

Prove via induction this recursively defined sequence

Let $P(n) = 2P(n-1) + n, P(1) = 3.$ Use induction to show that $$P(n) = 3(2^n) - n - 2$$ Highly verbose solutions are greatly appreciated.
1
vote
1answer
120 views

Prove $\frac {1} {1+x^2} = \sum^{n-1}_{j=0} (-1)^j x^{2j} + (-1)^n \frac {x^{2n}} {1+x^2}, x\in \mathbb R, n \in \mathbb N$ by induction

Prove $\frac {1} {1+x^2} = \sum^{n-1}_{j=0} (-1)^j x^{2j} + (-1)^n \frac {x^{2n}} {1+x^2}, x\in \mathbb R, n \in \mathbb N$ by induction. $n = 1$: $\sum^{(1)-1}_{j=0} (-1)^j x^{2j} + (-1)^n \frac ...
0
votes
3answers
62 views

Prove that $3+ 3\cdot5+…+3\cdot5^n = \frac{3(5^{n+1}-1)}{4}$ for all nonnegative integers.

I have been stuck on this one for a while. Supposed to use induction to prove that $3+ 3\cdot5+...+3\cdot5^n = \Large\frac{3(5^{n+1}-1)}{4}$ for all nonegative integers. I don't know if I'm taking ...
6
votes
4answers
104 views

Proof by induction that if $n \in \mathbb N$ then it can be written as sum of different Fibonacci numbers

Proof that every natural number $n\in \mathbb N$, can be written as the sum of different Fibonacci numbers between $F_2,F_3,\ldots,F_k,\ldots$. For example: $32 = 21 + 8+3 = F_8+F_6+F_4$ Research ...
2
votes
2answers
76 views

Proof by induction of a Fibonacci relation [duplicate]

We know: $F_0 = 0$ $F_1 = 1$ $F_i = F_{i-1} + F_{i-2}$ for $i \geq 2$ Prove by induction: $F_i = \dfrac{\phi^i-{\phi^{*}}^i}{\sqrt{5}}$ where $\phi = (1+\sqrt{5}) / 2$ and $\phi = (1-\sqrt{5}) / ...
-1
votes
1answer
44 views

Prove by Induction (Geometric Progression)

Prove by induction that for any real number $q≠1$ and any $n\in \mathbb N$ we have $ \sum_{i=0}^n q^i=\frac{q^{n+1}-1}{q-1} $
3
votes
3answers
223 views

Prove that, for any positive integer n: $(a + b)^{n} \leq 2^{n-1}(a^{n}+b^{n})$

Prove that, for any positive integer n: $(a + b)^{n} \leq 2^{n-1}(a^{n}+b^{n}) $ I tried induction theorem, when $n = 1$ it is obviously right. But, say $n=k$, It does not make sense since I cannot ...
0
votes
2answers
58 views

Proof by induction ${n\choose k }\le n^k$

Ok, so the question is to prove by induction that: $${n \choose k} \le n^k$$ Where $N$ and $k$ are integers, $k \le n$; How do I approach this? Do i choose a $n$ and a $k$ to form my base case?
1
vote
3answers
32 views

proof by induction - algebra mistake?

I have been working on this proof for a few hours and I can not make it work out. $$\sum_{i=1}^{n}\frac{1}{i(i+1)}=1-\frac{1}{(n+1)}$$ i need to get to $1-\frac{1}{k+2}$ I get as far as ...
0
votes
1answer
489 views

Fibonacci proof by Strong Induction

Prove by strong induction that for a ∈ A we have $F_a + 2F_{a+1} = F_{a+4} − F_{a+2}.$ $F_a$ is the $a$'th element in the Fibonacci sequence
1
vote
5answers
416 views

Invalid induction proof?

Prove the following using mathematical induction. If $a_{1}, a_{1}, ... , a_{n}$ are positive real numbers such that if $$a_{1}a_{2}...a_{n} = 1 $$ then $$a_{1}+a_{2}+ ... + a_{n} \geq n$$ My proof: ...
1
vote
2answers
50 views

How to prove this Mathematical Induction problem?

We got $n \geq 3$ lines drawn on a surface with conditions below: No two lines are parallel. No three lines make a conjunction in a specific point. Prove that one of the areas created by these ...
2
votes
1answer
119 views

How to prove this claim using Mathematical Induction?

We have $n$ points on a surface and for each $3$ points, we are able to put them into a circle with radius of unit length. Prove that all of these points are on circle with radius of unit length. My ...
1
vote
0answers
320 views

How to prove this equation using Mathematical Induction?

I was trying to prove this. I tried somehow but didn't get any idea. I think we can prove this using induction. I'd really appreciate it if you could help me. ...
1
vote
1answer
73 views

Stuck on inductive step: $2^x > x^n$ when $x\rightarrow \infty$

I want to show that $2^x > x^n$ when $x \rightarrow \infty$ for all $n \in \mathbb{N}$. I'm trying to do it by induction over $n$. The base case, $n = 1$, is true: $2^x > x$ when $x \rightarrow ...
1
vote
1answer
34 views

Prove that $P(n)$ can be proven by strong induction if and only if it can be proven by regular induction.

If $P(n)$ can be proven by strong induction, I know we can strengthen the inductive hypothesis to prove it by regular induction, right? But how would I do this?
0
votes
1answer
59 views

Question over regular induction: Let $P(n)$ be the statement that $n$-cent postage can be formed using just 4-cent and 7-cent stamps

Prove $P(n)$ is true for $n \geq 18$ using regular induction. I know how to do this problem using strong induction but don't know how to proceed using regular induction. I know the first step is ...
1
vote
3answers
239 views

Proof that $23^{n} - 1$ is divisible by $11$ for all positive integers $n$.

I'm having a bit of a problem proving this statement. Maybe someone can point me in the right direction? Best regards,
0
votes
2answers
99 views

Mathematical Induction

I've gotten to the final step and believe my problem lies within my algebra. Prove the following: $1 \times 3 + 2 \times 4 + 3 \times 5 + ... + N(N+2) = \frac{N(N+1)(2N+7)}6$ Here is my show that ...
0
votes
1answer
107 views

Proving an inequality for a sequence by induction

I'm having some trouble with the following problem: Let $a_n$ be a sequence defined iteratively for $n \geq 0$ as follows: $a_n = a_{m+1} + 2a_m + a_{n-m-1} + 2$ where $m$ is defined as ...
1
vote
1answer
44 views

Question over induction, suppose $P(n)$ is true for all positive integers $n$ that is a power of 2.

Suppose, that $P(k+1) \Rightarrow P(k)$ for all positive integers $k$. How would I prove $P(n)$ is true? I am getting confused since this is going the 'other way'. Usually $P(k)\Rightarrow P(k+1)$
1
vote
4answers
60 views

Prove that for all $n \in \mathbb{N}$: $2^{n-1}(a^n + b^n) \ge (a + b)^n$

Prove that for all $n \in \mathbb{N}$: $$2^{n-1}(a^n + b^n) \ge (a + b)^n$$ I used induction (for $k = 1,2,...n-1$), and ended up with the following equation: $$(a + b)(a + b)^{n-1} \le (a + ...
3
votes
1answer
170 views

Proof by induction - correct inductive step?

The problem: $$ x_1 \geq x_2 \geq ... \geq x_{3n} \geq x_{3n+1} \geq 0 $$ Show that: $$ x_1^2 - x_2^2 + ... - x_{3n}^2 + x_{3n+1}^2 \geq (x_1 - x_2 + ... - x_{3n} + x_{3n+1})^2 $$ I'm trying to ...
2
votes
0answers
163 views

Simple knapsack with arbitrary weights: Algorithm won't work, but my proof by induction doesn't agree.

We want to solve the simple knapsack problem: We're given a set of $n$ positive item weights, which are unique integers $\{w_1, \ldots , w_n\}$, and an integer $C > 0$, representing the capacity of ...
2
votes
5answers
105 views

Prove by induction that for all $n$, $8$ is a factor of $7^{2n+1} +1$

I want to prove by induction that for all $n$, 8 is a factor of $$7^{2n+1}+1$$ I have proved it true for the base case and assumed it true for $n=k$, but when I cannot figure out when to go towards ...
1
vote
0answers
58 views

Proof by induction for all positive integers

$\sum_{j=1}^n j^2 = \frac{n(n+1)(2n + 1)}{6}$ So I did the obvious and plugged one to show that $1^2 = \frac{1(1+1)(2(1) + 1)}{6}$ Now I am trying to show that $1^2 + 2^2 + ... + n^2 + (n + 1)^2 = ...
5
votes
3answers
147 views

If $z_{n+1}=\frac{27}{\overline{z_{n}}}+6$ and $z_1 = 3 + 6i$, then find $z_{n}$

Let the complex sequence $\{z_{n}\}$ satisfy $z_{1}=3+6i$, and $$z_{n+1}=\dfrac{27}{\overline{z_{n}}}+6.$$ Find the $z_{n}$. My idea: since ...
0
votes
2answers
64 views

Proof by Mathematical Induction.

Using mathematical induction I am to prove: $ \left( \begin{array}{ccc} 1 & 1 \\ 1 & 0 \end{array} \right)^n $ = $ \left( \begin{array}{ccc} F_{n+1} & F_n \\ F_n & F_{n-1} ...
0
votes
3answers
70 views

Mathematical Induction Proof

I am to use mathematical induction to prove: $\sum_{i=1}^n$ $(i \times i!) = (n+1)! - 1$ my base case is n = 1 $RHS: (1 \times1!) = 1$ $LHS: (1+1)! - 1 = 1$ If I am not mistaken the next step is ...
0
votes
1answer
43 views

Solving proof by induction row

Hello i am not able to figure out how to continue on this induction. I did work so far: What to do after that? UPDATED: so far: is it right?? but what about k + 1 it doesnt hold for 2^k
0
votes
2answers
41 views

What is the general stragety for conjecturing a formula based off a pattern?

Is it simply to guess and evolve a answer until it gets closer or is there an approach? Ex: Find the formula for: $a_k = \frac{a_{k-1}}{2} + 1$ where $a_0 = 1$. One would go: $a_1 = 3/2, a_2 = ...
-3
votes
1answer
41 views

How to prove this using induction?

The problem is : Using induction, prove that $ (\frac{n+1}{n})^n \le n $ for $ n>3 $ and then using that prove that the sequence $ 1 , 2 ^ {(1/2)}, 3 ^ {1/3},4^{1/4} .. $ is decreasing starting ...
0
votes
2answers
34 views

Trying to prove by induction but do not know where to start (Analysis)

I understand how induction works but I am stuck on how I should approach this problem. I know I could start with the base case, but I'm not sure if my approach would be a solid proof. Here is the ...
0
votes
2answers
98 views

Proving inequalities by using induction

For all $n\ge 2$ prove $n^2 \ge n+1$ by using induction. Here is my attempt at the problem. Base case: $n=2$, $2^2 > 2+1$, $4>3$ Inductive step: $p(k) = k^2 \gt k+1$ $p(k+1)=(k+1)^2 \gt ...
1
vote
1answer
71 views

Prove divisibility by using induction

Prove that for integers $n > 0$, $n^3 + 5n$ is divisible by $6$. Here is what I have done: Base Step: $n=1$, $1^3+5(1)=6$ Inductive Step: $p(k)=k^3 + 5k =6m$, $m$ is some integer ...
0
votes
6answers
135 views

Why is an algebra not a $\sigma$-algebra by induction?

I am studying probability theory by reading Sidney Resnick's "A Probability Path". On page 12 and 13, algebra and $\sigma$-algebra are defined. The only difference between the two is the third ...
1
vote
1answer
32 views

I'm not sure if my subscripts are lining up correctly in this elementary number theoretic induction proof

First, the motivation for the below lemma is to use in a proof that every number has a unique representation in a base. My question is that when using the inductive hypothesis, I'm not sure if my ...
1
vote
2answers
100 views

Meaning of variables and applications in lambda calculus

The wikipedia definition of lambda terms is: The following three rules give an inductive definition that can be applied to build all syntactically valid lambda terms: a variable, $x$, is ...
0
votes
2answers
41 views

Proof for a theorem using induction

I have to prove the following using mathematical induction: $ S(n)= \frac{1}{3}+ \frac{1}{9}+...+ \frac{1}{3 ^{n-1} }+ \frac{1}{ 3^{n} } = 0.5 - \frac{1}{2*3^{n} } $ I understand I have to do the ...
1
vote
1answer
67 views

Prove $n! \geq n^2$ for $n \geq 4$

I am working through a discrete math course, and have come upon a question that I don't understand how the solution was obtained. The question is, prove $n! \geq n^2$ Hypothesis: $p(n): n! \geq n^2, ...