Induction in general is the inference from the particular to the general. Mathematical induction is not true induction, but is a form of deductive reasoning. Its most common use is induction over well ordered sets, such as natural numbers, or ordinals. While induction can be expanded to class ...

learn more… | top users | synonyms

1
vote
1answer
58 views

Combinatorics identity sum of

Prove that: $$\sum^{n}_{k=0}\binom{k}{2n-k}2^k = 2^{2n}$$ By using only combinatorics identities.
2
votes
3answers
142 views

prove: $\dfrac{2^{n+1}+(-1)^n}{3}$

I am asked to prove this notation with induction for $n\in \mathbb{N}$: real problem is to fill the area with tilings. and for $n\in \mathbb{N}$ there are exactly so many chances to fill the area as ...
0
votes
0answers
92 views

Improper integral $\int_{0}^{\infty}\frac{x^n}{x^{m+n+1}} \ dx=\frac{n! {(m-1)}!}{(m+n)!}.$

How can I prove that $$\int_{0}^{\infty}\frac{x^n}{x^{m+n+1}} \ dx=\frac{n! {(m-1)}!}{(m+n)!}\quad ?$$ I tried to do induction on $n$ and on $m$, separately, but I could only do the base case ($n=1$ ...
2
votes
2answers
88 views

How to use induction to prove this argument?

It is obvious that this grammar will always return an equal number of both a's and b's. But I was wondering how to prove it using induction? I understand induction, but I was finding it hard to ...
2
votes
1answer
79 views

show by induction if there exists a $n_0 \in \mathbb N $such that $n\geq n_0 , n! \gt 2n^3$

I tried and I got there doesn't exist such a $n_0$ However, I dun think I have a formal proof for this. My approach is, First assume there is such a $n_o$ exist and start my calculation with ...
4
votes
3answers
368 views

Prove that $(a+1)(a+2)…(a+b)$ is divisible by $b!$ [duplicate]

The problem is following, prove that: $$(a+1)(a+2)...(a+b)\text{ is divisible by } b!\text{ for every positive integer a,b}$$ I've tried solving this problem using mathematical induction, but I ...
1
vote
2answers
551 views

proof by induction to demonstrate all even Fibonacci numbers have indices divisible by 3

I am practicing proof by induction, and would like to use induction to prove the following hypothesis about the Fibonacci numbers: $$(\forall n\ge0) \space 0\equiv n\space mod \space 3 \iff 0 \equiv ...
0
votes
1answer
142 views

Recursive Definitions with Converse

I think I know how to solve i. and ii., but not iii: Base Case: $(0,0) \in S$ Recursive Step: If $(a,b)\in S$, then $(a+1,b+2)\in S$ and $(a+2, b+1)\in S$. (For i and ii): Prove that if $(a,b) \in ...
2
votes
2answers
256 views

Another hat problem

A finite number of prisoners, after being given their hats (black or white), are able to see one another but themselves, and then they are ordered to jot down their guess on the color of their own ...
0
votes
2answers
75 views

Prove summation using induction [duplicate]

$$\sum\limits_{i=1}^n i^3 = \left(\frac{n(n + 1)}{2}\right)^2$$ My basis step is $P(1)$ sets the $LHS = RHS = 1$. For the inductive step, I assume $n = k$ holds for $k+1$. On the $RHS$: ...
0
votes
2answers
128 views

I need help with proofs using mathematical Induction

I need help with this problem: $2+7+12+17+...+(5n-3)=(\frac{n}{2})(5n-1)$
1
vote
1answer
85 views

Induction with compositions

Proposition. Suppose $g,h:\mathbb{R}\rightarrow\mathbb{R}, (g\circ h\circ g^{-1})^{n}=g\circ h^{n}\circ g^{-1}$ where $n\in\mathbb{N}$ and $g$ is a bijection. We will prove this by mathematical ...
12
votes
2answers
792 views

9 pirates have to divide 1000 coins…

A band of 9 pirates have just finished their latest conquest - looting, killing and sinking a ship. The loot amounts to 1000 gold coins. Arriving on a deserted island, they now have to split up the ...
3
votes
4answers
104 views

Induction proof: $\dbinom{2n}{n}=\dfrac{(2n)!}{n!n!}$ is an integer.

Prove using induction: $\dbinom{2n}{n}=\dfrac{(2n)!}{n!n!}$ is an integer. I tried but I can't do it.
2
votes
2answers
154 views

Induction on the Fibonacci sequence?

Prove by induction that the $i$th Fibonacci number satisfies the equality: $$F_i = \frac {\phi^i - \hat\phi{}^i}{\sqrt5}$$ where $\phi$ is the golden ratio and $\hat\phi$ is its conjugate. ...
6
votes
10answers
1k views

Prove by mathematical induction that $1 + 1/4 +\ldots + 1/4^n \to 4/3$

Please help. I haven't found any text on how to prove by induction this sort of problem: $$ \lim_{n\to +\infty}1 + \frac{1}{4} + \frac{1}{4^2} + \cdots+ \frac{1}{4^n} = \frac{4}{3} $$ I can't ...
7
votes
2answers
158 views

Fiboncacci theorem: Proof by induction

I have the following theorem to prove by induction: $$ F_{n} \cdot F_{n+1} - F_{n-2}\cdot F_{n-1}=F_{2n-1} $$ It is mentioned in my script that the proof should be possible only by using the ...
4
votes
4answers
172 views

If $S_n = 1+ 2 +3 + \cdots + n$, then prove that the last digit of $S_n$ is not 2,4 7,9.

If $S_n = 1 + 2 + 3 + \cdots + n,$ then prove that the last digit of $S_n$ cannot be 2, 4, 7, or 9 for any whole number n. What I have done: *I have determined that it is supposed to be done with ...
3
votes
1answer
73 views

Proving that $n|m\implies f_n|f_m$

Question: Let $m,n\in\mathbb{N}$, prove that if $n|m$, $F_n|F_m$. I've tried to use induction, but I don't really know where to start since there's $2$ numbers: $n$ and $m\ \dots$ I did induction ...
7
votes
2answers
192 views

Does this require transfinite induction?

Given any uncountable set S, would I need to use transfinite induction to prove if I remove single elements recursively, I will be left with the empty set? It seems like this can be thought of as an ...
2
votes
1answer
109 views

Prove $\sin((2n+1)x)$ function by induction

Can someone help me prove the following by mathematical induction: $$\sin((2n+1)x)=\sin(x)(1+2 \sum_{k=1}^{n} \cos(2kx))$$ I was told to use induction on $n$; however I keep getting stuck. Any help ...
1
vote
1answer
76 views

Proof by Induction solution not understood

Here is a question and solution but I don't understand what's happening after $m = m+1$. How does $(3(m+1))!$ equal $(3m)!(3m+1)(3m+2)(3m+3)$? Should it not be $(3m+3)!$? Same thing with the ...
2
votes
3answers
360 views

combinatorial argument and by induction proof

Let n be a fixed natural number. Show that: $$\sum_{r=0}^m \binom {n+r-1}r = \binom {n+m}{m}$$ (A): using a combinatorial argument and (B): by induction on $m$?
6
votes
4answers
203 views

Sum of the first $n$ triangular numbers - induction

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 ...
1
vote
2answers
133 views

Prove that for any $n \in \mathbb{N}, 2^{n+2} 3^{n}+5n-4$ is divisible by $25$?

I have question Q Prove that for any $n \in \mathbb{N}, 2^{n+2} 3^{n}+5n-4$ is divisible by $25$? by using induction Thanks
2
votes
2answers
95 views

Is mathematical induction necessary in this situation?

I was reading "Number Theory" by George E. Andrews. On P.17, where he proves that for each pair of positive integers a,b, gcd(a,b) uniquely exists, I came up with a question. The approach he used ...
1
vote
2answers
117 views

How can be done by the method of mathematical induction?

We are given that $P(x+1)-P(x)=2x+1$ We also know that $P(0)=1$ We want to prove that $P(2004)=(2004)^2 +1$ Can someone explain how can be solved with mathematical induction? Thank you in advance!
0
votes
3answers
74 views

How can I use induction solve this?

How can I show/solve this? I've tried by using the basis step and the inductive step, but just can't seem to get it right. $$\forall(n \geq 0)(4\mid(9^n − 5^n)).$$
1
vote
1answer
140 views

How to show by induction that, for $0<\theta<\pi$, $\det A_n=\frac{\sin (n+1)\theta}{\sin \theta}.$

I need help with the underlined part. Thanks in advance Let $A_n$ be the $n\times n$ matrix given by $$a_{ij}= \begin{cases} 0 & \text{if }|i-j|>1, \\ 1 & \text{if }|i-j|=1, ...
3
votes
2answers
88 views

Strong Mathematical Induction: Prove $3\mid b_n$ for a given recurrence relation $b_n$

Here is what I have so far: Proof $3\mid b_n$ for $n$ integers $\geq 1$ Base Cases both given $b_1=3, b_2=9$ and $b_n=6b_{n-2}+b_{n-1}$ $$P(1)=3\mid b_1$$ $$P(1)= 3\mid 3$$ Since $3\mid 3$, the ...
1
vote
1answer
445 views

Mathematical induction (sum of the first few even numbers)

So the question was basically " Suppose that there are n teams in a rugby league competition. Every team A plays every other team B twice, once at the home ground for team A, and the other time at the ...
1
vote
1answer
229 views

Generalized Josephus problem

I have been reading generalized Josephus problem from Concrete Mathematics. The recurrence form for the problem is given as f(1) = a f(2n) = 2f(n) + b, for n >= 1 f(2n+1) = 2f(n) + y, for n >= 1 ...
2
votes
4answers
87 views

mathematical induction

Suppose that $x > 0$ and let $n \geq 2$ be a positive integer. Prove that $(1 + x)^n \geq 1 + nx + \frac{n(n-1)}{2}x^2$ So for the base case, I have $x=1$, but that really is not getting me ...
1
vote
1answer
66 views

Question on the use of induction in the Electronic Mail Game

In Rubinstein's Electronic Mail Game, Player I and Player II's strategies take the form as $s_i : \mathbb{N} \to \{A,B\}$, $(i =1,2)$. Rubinstein shows that the pair of constant functions, $s_1(t_1) ...
2
votes
3answers
252 views

Prove By Mathematical Induction (factorial-to-the-fourth vs power of two)

Prove $(n!)^{4}\le2^{n(n+1)}$ for $n = 0, 1, 2, 3,...$ Base Step: $(0!)^{4} = 1 \le 2^{0(0+1)} = 1$ IH: Assume that $(k!)^{4} \le 2^{k(k+1)}$ for some $k\in\mathbb N$. Induction Step: Show ...
4
votes
1answer
1k views

Proving Inequality using Induction $a^n-b^n \leq na^{n-1}(a-b)$

I was trying to prove this inequality using induction, but couldn't do. Question: Suppose $a$ and $b$ are real numbers with $0 < b < a$. Prove that if $n$ is a positive integer, then: ...
13
votes
1answer
309 views

Prove $\sin(1/n)<1/n$ for all $n$

I need to prove $\sin(1/n)<1/n$ for all $n \in \Bbb N$ using mathematical induction. Dont know how to start. Please help!
1
vote
1answer
213 views

How to prove that $n^k = O(2^n)$

I'm having issues trying to prove this. The Big Oh definition is: f(n) = O(g(n)) if exists a real constant $c > 0$ and $n_0 \in \Bbb N $ in such a way that for all $n \ge n_0$ we have f(n) $\le$ ...
6
votes
4answers
617 views

$f: \mathbb{R} \to \mathbb{R}$ satisfies $(x-2)f(x)-(x+1)f(x-1) = 3$. Evaluate $f(2013)$, given that $f(2)=5$

The function $f : \mathbb{R} \to \mathbb{R}$ satisfies $(x-2)f(x)-(x+1)f(x-1) = 3$. Evaluate $f(2013)$, given that $f(2) = 5$.
0
votes
2answers
643 views

Flawed proof that all positive integers are equal

Suppose that we are trying to prove that for every positive integer n, if x and y are positive integers with max(x, y) = n, then x = y. For the base case, we suppose n = 1. If max(x, y) = 1 and x and ...
2
votes
2answers
178 views

Recursive algorithm correctness: problem.

Considering that to prove a recursive algorithm we should refer to mathematical induction. Given the following algorithm (which sort an Array of size r) I found that base cases are for array size of 0 ...
1
vote
2answers
2k views

A one-to-one function from a finite set to itself is onto - how to prove by induction?

I'm not sure if I can do this without knowing what f actually is? Let $X$ be a finite set with $n$ elements and $f: X \rightarrow X$ a one-to-one function. Prove by induction that $f$ is an onto ...
5
votes
3answers
2k views

Prove the following using induction on n (matrices)

Prove the following using induction on n: $$\begin{pmatrix} 2 & 1 \\ -1 & 0 \end{pmatrix}^{n} = \begin{pmatrix} n+1 & n \\ -n & -n+1 \end{pmatrix}$$ I know that multiplication of ...
2
votes
2answers
397 views

Induction proof [ little-o notation ]

I have to prove that $ 2^n = o(n!) $, that is, $ \forall c \gt 0 \quad \exists$ $ n_0 \in \mathbb N$ such that $ \forall n \ge n_0$ we have $ 2^n \lt c.n! $ Well, this is what I did so far: First I ...
0
votes
1answer
70 views

Prove by induction $ \sum^n_{i=1}(i-1/2) = n^2/2 $

This is a question from a test that I wrote and I'm wondering how do you solve it. Prove by induction that $$ \sum^n_{i=1}(i-1/2) = \frac{n^2}{2} $$ *Provide a Base Case, Inductive Hypothesis, and ...
2
votes
1answer
130 views

Confused on definition of Inductive set?

I am reading "Set theory, logic and their limitations" by Moshe Machover (page 264). If $\mathfrak {^*N}$ is an $\mathcal L$-structure and $X$ is any subset of $^*N$, we say that $X$ is inductive ...
1
vote
1answer
102 views

prove sum property by induction

Knowing that $(a_i)_{i\ge1}$ prove that $\forall n \in \Bbb N$: $$\sum^n_{i=1}ra_i=r\Big(\sum^n_{i=1}a_i \Big)$$ This kind of demonstrations is totally strange to me, I do not understand how to ...
1
vote
3answers
86 views

$P(n) = 2^n > n^2$, find $k \in \mathbb{N}$ so that $P(k) \Rightarrow P(k+1)$

I've got this problem where I need to find $k \in \mathbb{N}$ so that $P(k) \Rightarrow P(k+1)$ and $P(n) = 2^n \gt n^2$ By induction I have: $2 = 2^1 > 1^2 = 1$ which is ok with the first ...
0
votes
1answer
418 views

Solving Recurrence Relation with Forward Substitution

I've found myself quite stuck on this recurrence relation. I've been given it to solve, via forward substitution and verify using induction. I start out with $$ T(n) = 4T(n/3) $$ For all $n > 1$ ...
1
vote
1answer
656 views

Using mathematical induction to show that a binary tree of height $h$ has no more than $2^h$ leaf nodes

Use mathematical induction to show that a binary tree of height $h$ has no more than $2^h$ leaf nodes. I'm familiar with mathematical induction proofs, but I haven't encountered one like this. ...