# Tagged Questions

73 views

### Using induction to verify a statement

I have to prove that this statement is true. For $n = 1, 2, 3, ...,$ we have $1² + 2² + 3² + ... + n² = n(n + 1)(2n + 1)/6$ Basically I thought I'd use induction to prove this. Setting $n = p+1$, I ...
82 views

### Prove that $3^n>n^4$ if $n\geq8$

Proving that $3^n>n^4$ if $n\geq8$ I tried mathematical induction start from $n=8$ as the base case, but I'm stuck when I have to use the fact that the statement is true for $n=k$ to prove ...
58 views

### How to prove this inequality by using induction?

If $x,y$ are distinct real numbers such that $x+y>0$ and $n\ge 1$, then $2^{n-1}(x^n+y^n)\ge (x+y)^n$. It is obvious for $n=1$. How to do the rest by using induction?
46 views

### Combinatorics identity sum of

Prove that: $$\sum^{n}_{k=0}\binom{k}{2n-k}2^k = 2^{2n}$$ By using only combinatorics identities.
146 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 ...
50 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$: ...
113 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 ...
54 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: ...
47 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$ ...
59 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 ...
54 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 ...
86 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$ ...
48 views

### Formal definition of Mathematical Induction & Strong Induction

I have been reading some notes on Induction and Strong Induction and fully understand how they work. However I was interested in a formal/mathematical way of expressing their definition and was ...
36 views

124 views

117 views

### Something kind of like proving the euclidean Algorithm by induction

Let a > b be positive integers. In applying the Euclidean algorithm, we have $a = b q_0$ + $r_0$, $b = r_0 q_1 + r_1$, and $r_{n-1} = r_n q_{n+1} + r_{n+1}$, for all $n > 0$. Prove by induction ...