0
votes
1answer
46 views

Show that $f^{[n]}(0)=0$ for all $n=0,1,2…$

Let $$f(x)=\left\{ {\matrix{ {{e^{ - {1 \over {{x^2}}}}},x \ne 0} \cr {0,x = 0} \cr } } \right.$$ Show that $f^{[n]}(0)=0$ for all $n=0,1,2,\cdots$ The proof: First note that for ...
0
votes
2answers
40 views

Proof of the inequality $F_i<(5/3)^i$ for the Fibonacci numbers

The example states: As an example, we prove that the Fibonacci numbers, F0 = 1, F1 = 1, F2 = 2, F3 = 3, F4 = 5,..., Fi = Fi - 1 + Fi - 2, satisfy Fi < (5/3)i, for all i >= 1. To do this, we ...
2
votes
4answers
72 views

Prove that $133$ divides $11^{n+1} + 12^{2n−1}$ for all $n > 1$? [duplicate]

I have tried this question so hard but still stuck here. It seems like easily provable if all $n$ are all positive numbers but in this question, the $n$ is bigger than $1$. original question : prove ...
0
votes
0answers
38 views

Proof Strategy: Induction Summation of Series

Let $P(n)$ be the following statement: $$\sum\limits^{n}_{i=0}r^i = \dfrac{1-r^{1+n}}{1-r}\text{ for all }n \in \mathbb{N}\text{.}$$ I am stuck at the base case: $$P(1):1 + r = ...
1
vote
2answers
32 views

Use induction to prove trignometric identity with imaginary number

Prove by induction that if $i^2 = -1 $, then for every integer $n >= 1$, $[\cos(x) + i\sin(x)]^n = \cos(nx) + i\sin(nx)$. My solution so far: 1. It can be easily shown that it is true for n = 1. ...
7
votes
5answers
77 views

prove by induction $7 \mid 3^{3^n}+8$

Okay so ive been trying to prove this for about 5 hours... really need salvation from the geniouses around here. prove by induction $7\mid 3^{3^n}+8$ i really need some directions on what to do ...
4
votes
2answers
110 views

Prove that $\sqrt{n} \le \sum_{k=1}^n \frac{1}{\sqrt{k}} \le 2 \sqrt{n} - 1$ is true for $n \in \mathbb{N}^{\ge 1}$

I'm trying to solve these induction exercises proposed by the department of mathematics of Oxford University. I don't know how to give a valid proof for the third one which says the following: ...
1
vote
2answers
73 views

Better proof that $n \leq 2n$ for all natural numbers?

I tried proving via induction on naturals that $n \leq 2n$ for each natural $n$. Obviously, $0 \leq 2(0)$, and then assuming for any given $n$, $n \leq 2n$, you just show that $n + 1 \leq 2(n + 1).$ ...
4
votes
1answer
75 views

how to solve this elementary induction proof: $\frac{1}{1^2}+ \cdots+\frac{1}{n^2}\le\ 2-\frac{1}{n}$

this is a seemingly simple induction question that has me confused about perhaps my understanding of how to apply induction the question; $$\frac{1}{1^2}+ \cdots+\frac{1}{n^2}\ \le\ 2-\frac{1}{n},\ ...
1
vote
0answers
59 views

Prove: $a^m\cdot a^n \cdot a^p=a^{m+n+p}$

How can I prove the following: Prop.: let be $m,n,p \in \Bbb{N}$ and $a \in \Bbb{R}$ then $$a^m\cdot a^n \cdot a^p=a^{m+n+p}$$ ??? I thinked by induction and I must prove: 1) $a^0\cdot a^0 \cdot ...
3
votes
3answers
51 views

Prove that $2n+1 \leq 2^n$ for $n \geq 3$ using mathematical induction.

Question: $2n+1 \leq 2^n$, for all $n \geq 3$ I've tried: Basis: $P(3) = 7 \leq 8 $, so basis step is valid Pick an arbitrary value from the universe, $k \geq 3$ Inductive Step: $2k + 1 \leq ...
0
votes
1answer
37 views

Proof by induction and inequalities

I am stuck on this question: given $a_1a_2≤(\frac{a_1+a_2}{2})^2$ prove by induction of m that $$a_1a_2...a_p≤(\frac{a_1+a_2+...+a_p}{p})^p$$ where $a_i$ are all positive and real and $p=2^m$ (an ...
0
votes
0answers
43 views

Proof by Induction for Fundamental Thm of Arithmetic

Use induction to make our proof of the Fundamental Theorem of Arithmetic more rigorous. Recall that $p$ is prime iff for all $a,b\in\mathbb Z:p\mid(ab)$ implies $p\mid a$ or $p\mid b$. Prove that ...
1
vote
3answers
62 views

Use induction to prove that $2^n$ divides $(2n)!$ for any $n\in\mathbb{Z}_{\geq0}.$ [duplicate]

Use induction to prove that $2^n$ divides $(2n)!$ for any $n\in\mathbb{Z}_{\geq0}.$ How would you do the inductive step for this proof? I have the base case done.
1
vote
3answers
28 views

How is derived the inductive step in mathematical induction?

I am quite familiar with the algorithm of mathematical induction but I can't rationalize the inductive step very well. Suppose I have the classical example: $$0 + 1 +2 + \ldots + n = ...
3
votes
3answers
54 views

Is it possible to use mathematical induction to prove a statement concerning all real numbers, not necessarily just the integers? [duplicate]

I am referring to the part of proof by mathematical induction where you show that "if it is true for one value k then it is true for the value k+1". Does proof by induction work over all real numbers? ...
1
vote
1answer
32 views

Inductive step assumption for all numbers up to $n$

I know that the inductive step should be "for all $n$ (if $P(n)$ then $P(n+1)$)" and NOT "if (for all $n$ $(P(n)$)) then (for all $n$ ($P(n+1)$))" - see this answer. But can it be like "if (for all ...
2
votes
5answers
111 views

Proof via induction $1\cdot3 + 2\cdot4 + 3\cdot5 + \cdots + n(n+2) = \frac{n(n+1)(2n+7)}{6}$

(b) Prove that for every integer $n \ge 1$, $$1\cdot3 + 2\cdot4 + 3\cdot5 + \cdots + n(n+2) = \frac{n(n+1)(2n+7)}{6}$$ This is the second part of a two part question. Part (a) was the following: ...
0
votes
2answers
57 views

Prove that for every integer $n \ge 1$, $1 + \frac{1}{\sqrt{2}}+\frac{1}{\sqrt{3}}+ … +\frac{1}{\sqrt{n}}\le 2\sqrt{n}$

I understand that this is an induction question. I start with the base case (n=1): $$1 < 2 \tag{That works!}$$ Induction step: Assume the statement works for all $n = k$, Prove for all $n = ...
0
votes
0answers
25 views

Proof by Induction on two languages [duplicate]

I have a question that states - Using proof by induction, prove formally that L(R*) = L((R*)*) -- Where R is a regular expression over a non-empty alphabet. I have am struggling to relate it back to ...
7
votes
2answers
130 views

Prove That the Second Moment is Minimized with a Circle Packing

Graham and Sloane studied the problem of minimzing the second moment of disks on the plane, i.e. minimize $$ U = \frac{1}{d^2} \sum_{i=1}^{n} || \mathbf{p}_i - \bar{\mathbf{p}} ||^2 $$ s.t. ...
0
votes
1answer
21 views

Factoring for Strong Induction for Fibonacci Sequence

Fibonacci: prove the following theorem: define the Fibonacci sequence $\left\{ a_n\right\}_{n=0}^{\infty}$ by $a_0=a_1=1$ and for integers $k>1$, $a_k=a_{k-1}+a_{k-2}$. Then, for each integer $n$, ...
0
votes
2answers
59 views

Proof by induction sum $2^j = 2^{n+1} - 1$

I am trying to solve a previous test for an exam, and there are no solutions. The problem I am trying to solve is If $n$ is a natural number, then $1 + 2 + 2^2 + 2+3 + ... + 2^n = 2^{n+1} -1$ ...
0
votes
3answers
59 views

Induction, show that something is smaller then …

I have to show the following by induction. $1 \cdot 2 \cdot 3 ... (n - 1) \leq (\frac{n}{2})^{n -1}$ As it is homework I "only" need a push in the right direction. my thought is that is something ...
1
vote
4answers
117 views

proof by induction: sum of binomial coefficients

Question: Prove that the sum of the binomial coefficients for the nth power of $(x + y)$ is $2^n$. i.e. the sum of the numbers in the $(n + 1)^{st}$ row of Pascal’s Triangle is $2^n$ i.e. prove ...
0
votes
1answer
30 views

Inductive Proof Recursive Definition

Using this recursive Definition: $$a_{n} = \left\{\begin{matrix} 4 & n=1\\ a_{n-1}+4n-5 & n \geq 2 \end{matrix}\right.$$ I somehow have to prove using induction $$a_{n} = 2n^{2} - ...
0
votes
1answer
43 views

Fibonacci Proof with Induction [duplicate]

$$f(n) = \left\{\begin{matrix} 0 & n=1\\ 1 & n=2\\ f_{n-1} + f_{n-2} & n\geqslant 2\end{matrix}\right.$$ How can I prove by induction that $$f_{n} \geq \left ( 1.5 \right )^{n-1}$$ ...
2
votes
2answers
58 views

Fibonacci Proof Using Induction

$$f(n) = \left\{\begin{matrix} 0 & n=1\\ 1 & n=2\\ f_{n-1} + f_{n-2} & n\geqslant 2\end{matrix}\right.$$ How can I prove by induction that $$f_{n} \leq \left ( \frac{1+\sqrt{5}}{2} ...
0
votes
3answers
38 views

Divisibility proof by induction.

$ 169$ | $3^{3n+3}-26n-27$ ? Fulfilled for $n=0$. Induction to $n+1$: An integer $x$ exists so that $ 169x= 3^{3n+6}-26n-27-26$ $ 169x= 27*3^{3n+3}-26n-27-26$ $ 169x= 26*3^{3n+3}+3^{3n+3}-26n-27-26$ ...
0
votes
3answers
32 views

Induction summation proof

Don't want a full answer but can somebody help me in the right direction with this problem. Have to prove using induction $$\forall n \geqslant 2: \sum_{i=1}^{n} \frac{4}{5^{i}} < 1$$
1
vote
1answer
44 views

How would I solve this mathematical induction proof? I am stuck after the first part of the induction.

$$1 + 5 + 5^2 + \ldots + 5^n = \frac{5^{n+1}-1}{4}$$ Basis case $n= 0$: $1^0 = 1 \;\;\;\;\;\;\;\;\;\;\;\; \frac{5^{1+1}-1}{4}=1$ Assume true for $n=k$: $$1 + 5 + 5^2 + \ldots + 5^k = ...
1
vote
1answer
62 views

Proof by induction: $2^n > n$

Base is $2^1 > 1$. Now we assume $2^n > n$ and try to obtain $2^{n+1} > (n+1)$. If I can use $2^n > 1$, I could just add that to $2^n > n$ and get $2^{n+1} > (n+1)$ but I don't ...
1
vote
0answers
215 views

Can I use Strong Induction to prove graph theory? - Hamilton Path/Tournament Graphs

I am working on the below proof. I am still new to proves so I am wondering if you guys can answer the following questions: 1) Did I use the inductive hypothesis correctly here? (By the inductive ...
0
votes
1answer
34 views

Help with multiple statement induction proof

I am learning proof by induction in my math class and I am having trouble with this problem: Prove that for $k \in N, 3^{4k-3}\equiv 3 \pmod{10}, 3^{4k-2} \equiv 9 \pmod{10}, 3^{4k-1} \equiv 7 ...
0
votes
5answers
105 views

Help with proof using induction: $1 + \frac{1}{4} + \frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$

I am having trouble with the following proof: For every positive integer $n$: $$1 + \frac{1}{4} + \frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$$ My work: I have tried to add ...
0
votes
1answer
104 views

[Beginner]How to tackle mathematical proofs?

So I recently joined university for a BSc in mathematics. I have never been exposed proofs but I have knowledge of algebra, trigonometry, and some differentiation/integration. Now I'm struggling with ...
1
vote
1answer
74 views

Is This a Proof by Induction?

Prove, disprove, or give a counterexample: $$\sum_{i=0}^n \left(\frac 3 2 \right)^i = 2\left(\frac 3 2 \right)^{n+1} -2.$$ I went about this as a proof by induction. I did the base case and ...
2
votes
1answer
168 views

Proving that $\,\sqrt [n] n < 1 + \sqrt{\frac{2}{n}}\,$ for all positive $n$

Hello 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 ...
0
votes
2answers
58 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
36 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
54 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
109 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 ...
3
votes
3answers
138 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 ...
2
votes
4answers
141 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 ...
0
votes
1answer
22 views

Proving by induction propositions of the type $P(n_1, n_2, …, n_k)$, where $n_1, n_2, …,$ and $n_k$ are natural numbers

For example: I've seen proofs of the multinomial theorem that use induction in the number of terms that are elevated at some power, but none that use induction in the exponent instead of using it in ...
1
vote
2answers
61 views

Proving a summation involving binomial coefficients.

I need to prove the following inductively: (http://upload.wikimedia.org/math/9/e/5/9e57871ba17c1ad48e01beb7e1bb3bb9.png) $$\sum_{i=1}^{n} i{n \choose i} = n2^{n-1}$$ And for the life of me I can't ...
0
votes
0answers
28 views

Validity of a proof by induction

By intuition, I would say that if L1 is a subset of L and that L is regular, then L1 is also regular, because L1 has less states than L2 and therefore there must be an automata for L1 too. However, ...
0
votes
2answers
103 views

Proving that $fib(n) < (5/3)^n$ for $n \ge 1$ by induction

I know this has been shown before here but no post really answered my question. I had this problem given to me as an induction practice problem and I couldn't solve it without help. When I got the ...
3
votes
2answers
237 views

Fallacious Induction Proof that All Integers are Equal [duplicate]

We're currently learning about induction in my real analysis course. I came up with the following proof that is obviously false but cannot quite figure out why it fails. Here it is... "Any set $S$ of ...
2
votes
1answer
128 views

Prove by induction that $2^{2n} – 1$ is divisible by $3$ whenever n is a positive integer.

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 ...