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

2
votes
1answer
112 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
314 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
54 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
227 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
98 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
105 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
57 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
155 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
103 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
60 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
68 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
42 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
40 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
40 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
85 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
131 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
93 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
65 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, ...
2
votes
1answer
67 views

Induction on exponent rule for groups

Prove: $(a^k)^m = a^{km}$ for all $k, m$ integers. Attempt: I am looking at the case where $m < 0$ and $k >0$. I am doing induction on a positive integer $m$, but $-m$ will become a negative ...
2
votes
4answers
366 views

prove by induction: $3 + 5 + 7 + … + (2n+1) = n(n+2)$

Use the principle of mathematical induction to prove that $$3 + 5 + 7 + ... + (2n+1) = n(n+2)$$ for all n in $\mathbb N$. I have a problem with induction. If anyone can give me a little insight ...
1
vote
0answers
51 views

induction on power elements in a group

Exercise: Prove by induction the following facts about power elements in a group. For all integers $k$ and $l$, $(a^k)^{l} = a^{kl}$ I am having trouble with induction on two integer variables. ...
0
votes
2answers
42 views

Math Induction to prove recursion

This is a problem from a practice test. I don't understand how the answer was produced using math induction. And yes, math induction is required for this problem. Define a function f: $\mathbb{N}$ ...
2
votes
2answers
89 views

Can someone help me with this proof?

Prove that $$1^2-2^2+3^2...+(-1)^{n-1}n^2=(-1)^{n-1}\frac{n(n+1)}{2}$$ whenever $n$ is a positive integer. I used $2$ as my base case and it worked. Then I plugged in $k$ for $n$. Now I can't figure ...
1
vote
6answers
237 views

Prove that ${n^5 - n}$ is divisible by 5 [duplicate]

I need to prove by induction if ${n^5 - n}$ is divisible by 5 and I have no idea how I would do it. I am trying to prove it for several hours now, I started with ${n^5 - n} \mod 5 = 0$ but then I ...
0
votes
3answers
62 views

Induction problem: “if the group has at least one player who is better than Messi, then all the members of the group are better than Messi”

I'm having some trouble with the following problem: "A french man is trying to prove that any non empty group of french soccer players satisfies the following: 'if the group has at least one player ...
1
vote
1answer
35 views

Is it obvious that $\sum_n x_n = 0 $ when $x_n = 0 ~ \forall n \in \mathbb N$?

Until recently I used to think that because of induction, a statement $P_n$ which is true $\forall n \in \mathbb N$ was also true when $n \to \infty$. Life was simple, and I was happy. Then someone ...
2
votes
2answers
165 views

Got stuck in proving monotonic increasing of a recurrence sequence

I'm stuck with the prove of the following recurrence sequence which was part of and old exam. $a_1:=\frac{1}{2}, a_{n+1}:=a_n(2-a_n)$ for $n \in \mathbb{N}$ I have to show that $0 <a_n < 1$ ...
0
votes
2answers
99 views

Proof by Induction - Sequence of integers

Suppose a sequence of integers $a_1$, $a_2$, ... is defined as: $$a_1 = 3$$ $$a_2 = 6$$ $$a_n = 5a_{n-1} - 6a_{n-2} + 2$$ for all $n\ge3$ $\mathbf {Prove}$ $\mathbf {S(n)}$: $a_n = 1 + 2^{n-1} + ...
0
votes
2answers
58 views

proof by strong induction of single variable with exponent

$x^n + \frac{1}{x^n} \in \mathbb{Z}$ (is an integer), for all positive integers $n$, where $x$ is rational. I've surmised that the only rational numbers that satisfy $x$ are 1 and -1. Thus, as you ...
0
votes
1answer
46 views

Prove that $n^2 < 2^n$ for all $n \geq 6$

My approach to solving this: By induction. (1) $S(n) = (n^2 < 2^n)$ for all $n \geq 6$, $n \in \mathbb N$. (2) Base Case: $n = 6$ $$6^2 < 2^6$$ $$36 < 64$$ So the statement is true for ...
1
vote
2answers
154 views

Strong Induction: Finding the Inductive Hypothesis

Consider this claim: Every positive integer greater than 29 can be written as a sum of a non-negative multiple of 8 and a non-negative multiple of 5. Assume you are in the inductive step and trying ...
0
votes
1answer
89 views

Permuation, disjoint cycles proof by induction.

I am having a hard time writing out a general proof. Can anyone please help? Thank you. Exercise: Show that any k-cycle (a1,......,ak) can be written as a product of some number of (k-1) 2-cycles. ...
3
votes
2answers
85 views

If I'm asked to prove that $n \le m$, is it sufficient to show that $n < m$?

I have a homework question, which is to prove by induction that $\sum\limits_{r=1}^{n} \frac{1}{\sqrt{r}} \leq 2\sqrt{n}$ for every integer $n \geq 1$. I've managed to show by induction that ...
0
votes
2answers
58 views

Induction with multiple variables

Let the function g : R $\rightarrow$ R satisfy $g(xy) = x \cdot g(y) +y \cdot g(x)$ for all real numbers x and y. Prove $g(u^n) = nu^{n-1}g(u)$, for all positive integers $n$ and all real numbers ...
0
votes
1answer
70 views

Induction proof of function from $\mathbb R$ to $\mathbb R$

Let f be a function from $\mathbb R$ to $\mathbb R$ satisfying $f(\frac{x_1+x_2}{2})=\frac{f(x_1)+f(x_2)}{2}$ Prove that for any positive integer $n$ we have ...
2
votes
1answer
53 views

Prove GM-AM inequality using induction

Show that $G_{2^n}\le A_{2^n}$ by using induction on n. I've proven the base case in the previous exercise: Let $G_2=\sqrt{a_1a_2}$ and $A_2=\frac{1}{2}(a_1+a_2)$ and $a_1,a_2 \in \mathbb{R}$ ...
-4
votes
2answers
189 views

Induction of $A_i$ [duplicate]

The base case $n=1$: $B\cup\left(\bigcap_{i=1}^1A_i\right)=B\cup A_1$ and $\bigcap_{i=1}^1(B\cup A_i)=B\cup A_1$. Now, suppose inductively that ...
-1
votes
2answers
56 views

Discrete Math: Ways to Prove Induction

The point of mathematical induction is to prove $\forall x\geq b[P(x)]$ by instead proving $P(b)\wedge \forall x\geq b[P(x)\rightarrow P(x+1)]$ ($b$ is often, but not always, $0$ or $1$). However, ...
2
votes
2answers
90 views

PROVE if $x \ge-1 $then $ (1+x)^n \ge 1+nx $ , Every $n \ge 1$

Use mathematical induction to prove this. Here is my answer but I stuck at certain point. Base Case: n=1 $$(1+x)^1 \ge 1+x $$ True , Induction Case: n=k assume $$(1+x)^k ...
-1
votes
2answers
197 views

Proof by induction that $B\cup (\bigcap_{i=1}^n A_i)=\bigcap_{i=1}^n (B\cup A_i)$

$\displaystyle B\cup (\bigcap_{i=1}^n A_i)=\bigcap_{i=1}^n (B\cup A_i)$ I was able to prove this without using induction, however I am supposed to prove it using induction. How should I go about ...