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

0
votes
1answer
33 views

Factorial and induction

Part of step in induction: $(2 k+1)*((1*3* 5*\dotsb* (2k-1)) =1*3*5*\dotsb*(2k+1)$ Am I correct with believing that we in first instance went up to $k$, and then we went further to $2((k+1)-1$ hence ...
1
vote
1answer
58 views

Proof of product summation of binomial coefficients

when I try to proof the sum of two independent negative binomial distribution to be negative binomial, I end up with how to proof the following identity. I try the induction but after I rearrange the ...
0
votes
1answer
20 views

Induction on String? (automata related)

Honestly, all I know about mathematical induction is as follow: prove $P(0)$ - base step for all $n \ge 1$, prove $(P(n − 1) \rightarrow P(n))$ - inductive step Prove the following claim by ...
3
votes
1answer
35 views

Can I extend mathematical induction to real numbers? [duplicate]

Here is my rather simple idea. I will treat the set of real numbers as a set of discrete continuities, each separated by an Epsilon ball that tends to 0. So, let's say P(b) is true. We then assume ...
0
votes
0answers
14 views

Induction to find string length equivalence

Rewrite system of RRR ≡ NULL, FF ≡ NULL, RRF ≡ FR. Show that each string in {F,R}* is equiv. to one of the six strings: NULL, R, RR, F, FR, FRR. A hint is to use induction and ask if every string of ...
0
votes
1answer
20 views

Show that $U_{n+1}-1<1/2(U_n-1)$

Given that U_0=3/2 $U_{n+1}=U_n^2-2U_n+2$ Show that $1<U_n<=3/2$ I did it by induction Then we have to show that $U_{n+1}-1<1/2(U_n-1)$ And deduce that $U_n-1<=(1/2)^{n+1}$ Then we ...
2
votes
1answer
45 views

Use induction to prove that any (finite) list is a permutation of itself—in other words, that the permutation relation is reflexive.

I'm having a bit of trouble with starting this proof by induction. I'm given that the definition of a permutation is: List a is a permutation of list b if any of the following are true: • list a and ...
1
vote
0answers
38 views

How do you express $\sum_{j=1}^{n} j^{k+1}$ in terms of $\sum_{j=1}^{n} j^{k}$?

I am trying to use induction to prove, for every positive integer $k$, that $$\sum_{j=1}^{n} {j^{k}} = \frac{n^{k+1}}{k+1} +\frac{n^k}{2} + P_{k-1}(n)$$ where $P_{k-1}$ is a polynomial of degree at ...
0
votes
1answer
65 views

Use Induction to prove that for all $n \in \mathbb{N}, (x^n + \frac{1}{x^n}) \in \mathbb{Z}$ if $x+\frac{1}{x}\in\mathbb{Z}$.

Assume $x \in \mathbb{R}$ and $(x + \frac{1}{x}) \in \mathbb{Z}$. Use Induction to prove that for all $n \in \mathbb{N},~ (x^n + \frac{1}{x^n}) \in \mathbb{Z}$. I'm not sure how to use the ...
3
votes
0answers
19 views

Product of the Euler phi function [duplicate]

Prove the following statement: If $n, m\in\mathbb{Z} $ and $g=$gcd$(n, m) $ then is $$\varphi(m, n) =\frac{ \varphi(m) \varphi(n) g} {\varphi(g)}. $$ Hint: Prove the statement with induction above ...
2
votes
0answers
50 views

Does it make sense to claim that something cannot be proven without induction? [duplicate]

Often we have questions on this site which ask for a proof of some result without induction.1 It seems that when such a question is posted, it is quite well-understood what is meant by proof avoiding ...
2
votes
4answers
60 views

Induction: Prove that $5^{3n} + 7^{2n-1}$ is divisible by $4$

Prove that $5^{3n} + 7^{2n-1}$ is divisible by $4$ for all $n \in \mathbb{N}$. For $n=1$, $\Rightarrow 5^3 + 7^1 \Rightarrow 132 \mid 4$ (which is divisible by $4$) Let us assume given equation ...
0
votes
0answers
15 views

Find all $n$ so that the weights can be split into two groups

There is a set of $ n$ coins with distinct integer weights $ w_1, w_2, \ldots , w_n$. It is known that if any coin with weight $ w_k$, where $ 1 \leq k \leq n$, is removed from the set, the ...
4
votes
3answers
107 views

Induction on inequalities (a sum less than a particular value) [duplicate]

I am trying to solve this inequality by induction. I just started to learn induction this week and all the inequalities we had been solved were like an equation less than another equation (e.g. $n! ...
0
votes
5answers
56 views

how can we prove the equality between number of vertices and sides of a polygon?

We know that a triangle is composed of 3 vertices and 3 sides,a square is composed of 4 vertices and 4 sides,a pentagon has 5 vertices and 5 sides. Can we prove by induction (or any other method) that ...
2
votes
2answers
56 views

Induction proof without summation

I have to prove this induction: $\dfrac{1}{(n+1)}+\dfrac{1}{(n+2)}+\dots+\dfrac{1}{2n} = \dfrac{1}{(1\times2)}+\dfrac{1}{(3\times4)}+\dots+\dfrac{1}{(2n-1)\times2n}$ Can someone help me with it?
2
votes
2answers
133 views

On what sets other than $\mathbb{N}$ might we use proof by induction?

Suppose we have a set $S$ with $s_1\in S$ and $f: S\to S$ and $n\subset S$ such that $n=\{s_1, f(s_1), f(f(s_1)), \cdots \}$ ($n$ not necessarily infinite). To establish properties of $n$, can we ...
5
votes
5answers
58 views

Use an induction argument to prove that for any natural number $n$, the interval $(n,n+1)$ does not contain any natural number.

Use an induction argument to prove that for any natural number $n$, the interval $(n,n+1)$ does not contain any natural number. I don't know where I could go with an induction argument. I was ...
5
votes
7answers
95 views

Showing that for $n\geq 3$ the inequality $(n+1)^n<n^{(n+1)}$ holds

I aim to show that $$(n+1)^n<n^{(n+1)}$$ for all $n \geq 3$. I tried induction, but it didn't work. What should I do?
0
votes
1answer
21 views

What is the biggest computation one should use for an induction base

First of all sorry for me (informal) language here - i am not a native english speaker. I have tried to look up my question here but couldnt find anything. I also tried to look it up on google but i ...
0
votes
1answer
70 views

Proof of inequality involving multiplicative function?

The identity below seems true for the examples I've considered. I thought I had proven it using induction but found a mistake and removed my attempted proof since it is not helpful. Given: $P(z)$ is ...
6
votes
6answers
157 views

Proof of induction principle, Proof falsification

I just had a very frustating conversation with one of my Professors. I'm tutoring for a lecture course on Analysis and in the lecture he gave a proof of the induction principle. I was trying to tell ...
-4
votes
1answer
29 views

Prove by mathematical induction that $(1+a)^n \geq 1 + n a$, for $n \geq 1$ and $a \geq 0$ [duplicate]

As the title says Prove by mathematical induction that for n ≥ 1 it is true that $(1 + a)^n \geq 1 + na$ for $a \geq 0$ Having no clue on how to solve this
1
vote
2answers
51 views

Is mathematical Induction possible in this situation?

Is mathematical Induction possible with this sigma sign? $\sum_{k=1}^{n} ((-1)^{n-k} * b^{n-k}) = \frac{b^{n}+1}{b+1}$ with $n = 2s+1 ; s \epsilon \mathbb{N}$ Statement: $\sum_{k=1}^{n} ...
-1
votes
5answers
38 views

Divisibility by 101; a problem with induction [closed]

I was trying to show that $10^{2n}+(-1)^{n+1}$ is divisible by $101$. Would anyone help me with the induction step please?
0
votes
0answers
32 views

Modulus-amplifying polynomials

I'm trying to prove that the family of polynomials $\lbrace P_k \rbrace$ defined as follows \begin{equation*} P_k(x) = (-1)^{k+1}(x-1)^{k} \left( \sum_{j = 0}^{k-1} \binom{k+j-1}{j} x^j \right) + 1. ...
0
votes
1answer
25 views

Using induction for an easy proof for formal languages

I am having trouble to understand the way of using a induction for the following example: Let $\Sigma \overset{\Delta} = \{a, b\}$ and $S_1 \overset{\Delta} = \{a^n \mid n \in \Bbb N\}$. Prove ...
5
votes
2answers
74 views

Geometrical proof by induction

Given a segment $AB$ of length $1$, define the set $M$ of points in the following way: it contains the two points $A,B$ and also all points obtained from $A,B$ iterating the following rule: for ...
-1
votes
1answer
51 views

Using induction to prove a description of a formal language [duplicate]

One of my tasks is to proof that something is correct or incorrect using induction. Since I am from Germany and don't know the right word in English I do my best to give all necessary info. We are ...
0
votes
1answer
18 views

Prove by induction the number of edges in a tree given the leaves.

Define a cs130A tree to be a single leaf node or an internal node (the root) connected to two disjoint subtrees, which are themselves cs130A trees. Prove by induction that for all cs130A trees the ...
0
votes
3answers
60 views

Prove that $6^{n+1} + 4$ is divisible by 4

I hope you can understand me, English isn't my main language. I have a superior algebra problem that I can't solve. Prove that for every n in Natural numbers ($N$) $$6^{n+1} + 4$$ is divisible ...
1
vote
2answers
55 views

Induction with $n+2$

When proving something via induction, is one allowed to do the induction step, showing that the conditions work for $n+2$, instead of $n+1$?
3
votes
1answer
77 views

Setting up a Problem for Induction that Involves Inequality and a Function

The problem states: Use mathematical induction to prove that any stack of ($n\geq 5$) pancakes can be  sorted using at most $2n-5$ flips.  You may use the fact  any stack of $5$ pancakes can be  ...
0
votes
0answers
28 views

General Chinese remainder theorem proof

Okay, so we have the Chinese Remainder Theorem: If $m_1$ and $m_2$ are coprime then the simultaneous congruences $\left( x \equiv a_1 \mod m_1 \right)$, $\left( x \equiv a_2 \mod m \right)$ have a ...
1
vote
4answers
78 views

Prove by induction that $8^{n} − 1$ is divisible by $7$

Prove by induction that $8^{n} − 1$ for any positive integer $n$ is divisible by $7$. Hint: It is easy to represent divisibility by $7$ in the following way: $8^{n} − 1 = 7 \cdot k$ where k is a ...
-1
votes
1answer
38 views

Show that $\sin(\frac{x}{2})(\sin(x)+\sin(2x)+…+\sin(nx))=\sin(\frac{nx}{2})\sin(\frac{n+1}{2}x)$ [duplicate]

I want to show that $\sin(\frac{x}{2})(\sin(x)+\sin(2x)+...+\sin(nx))=\sin(\frac{nx}{2})\sin(\frac{n+1}{2}x)$ But I'm not quite sure how to start my proof. I tried to expand the left half of the ...
1
vote
1answer
35 views

$\sum_{k=1}^{n}k(k-\frac{1}{3}) = \frac{n}{6}(an^2+bn+c)$ by induction

Find constants $a$, $b$ and $c$ such that for all $n \in \mathbb{N}$ $~~\sum_{k=1}^{n}k(k-\frac{1}{3}) = \frac{n}{6}(an^2+bn+c)$ Hints: you may want to find $a, b$ and $c$ from the condition ...
1
vote
0answers
42 views

Problem with induction of binomial coefficiency

(Sorry for making up math language, I am roughly translating math terms here) This is part of some of the induction exercises in the book "Otto Forster: Analysis 1" (1.2): ...
0
votes
1answer
32 views

Proving inequality with induction

$$ 0!+1!+...+n! \leq n!\bigg(\dfrac{1}{0!}+\dfrac{1}{1!}+...+\dfrac{1}{n!}\bigg) $$ How can I prove this inequality for $n\geq 1$? Actually I can see that when you divide both sides with $n!$ lhs is ...
4
votes
2answers
39 views

Is my inductive proof correct?

Trying this again. Given $f(n) = 2f(n-1) + 1$ with $f(0) = 0$, I guess that $f(n) = 2^n-1$. Base case: $f(0) = 2^0 - 1 = 1 - 1 = 0$, true. Inductive step: Suppose $f(n) = 2^n-1$ for some $n \geq ...
1
vote
3answers
90 views

Now am I doing induction correctly?

Recursion: $L_n = L_{n-1} + n$ where $L_0 = 1$. We guess that solution is $L_n = \frac{n(n+1)}{2} + 1$. Base case: $L_0 = \frac{0(0+1)}{2} + 1 = 1$ is true. Inductive step: Assume $L_n = ...
6
votes
4answers
109 views

Prove: $\forall$ $n\in \mathbb N, (2^n)!$ is divisible by $2^{(2^n)-1}$ and is not divisible by $2^{2^n}$

I assume induction must be used, but I'm having trouble thinking on how to use it when dealing with divisibility when there's no clear, useful way of factorizing the numbers.
3
votes
4answers
77 views

Proof by inducation $4n < 2^n$ for $n \geq 5$. [duplicate]

I'm looking here http://www.purplemath.com/modules/inductn3.htm and i want to prove: For $n \geq5, 4n < 2^n$. Base case: sub the first value, in our case n = $5 => 20 < 32$. Great. I ...
-1
votes
1answer
45 views

Prove the limit using mathematical induction and L'Hospital's rule. [closed]

Prove that for every $c>0$ and for every polynomial $p(x) \in \mathbb{R}[x]$ the limit $\lim\limits_{x \to \infty}{\frac{p(x)}{e^{cx}}}$ exists and is eqaual to $0$. Use the L'Hospital's Rule and ...
2
votes
1answer
31 views

Conjecture for the maximum number of rooms.

The puzzle I have is essentially this, but for $n$ rows.For this instance of $n=5$, quick tallying reveals the answer to be $21$. For $n=4$, it is $13$. For $n=3$, it is $7$. For $n=2$ it is $3$. ...
1
vote
2answers
63 views

Induction and contradiction

I want to prove a statement by induction , I tasted the base case, then I considered the induction hypotesis for n , so I assumed by absurd that is not true for n + 1 but this contradicts the ...
2
votes
0answers
46 views

Knuth algorithm on constructing a proof

I'm going through mathematical induction section of Knuth's book "The Art of Computer Programming" (pg. 11). I'm having a hard time understanding Algorithm I on constructing a proof. Here is the ...
2
votes
1answer
94 views

Showing that $3^{(3^n - 1)}$ divides $(3^n)!$

I am trying to solve the following by using induction: Show that $3^{(3^n - 1)}$ divides $(3^n)!$ for any non-negative integer $n$. But isn't the question incorrect, since it doesn't hold for ...
1
vote
0answers
37 views

How to correctly set up inductive proofs?

In practice, do you do some work on the inductive step and then reverse your steps? For example. Say you have this recurrence: $f(n+1) = 2f(n) + 1$ with $f(0) = 0$ This creates the sequence $0, 1, ...
0
votes
0answers
26 views

Prove that every natural number, bigger than 7, can be presented by sum of threes and fives? [duplicate]

How to prove that every natural number, bigger than 7, can be presented as a sum of threes and fives? e.g. $21=5*3+3*2$, $58=5*11+3*1$ etc.